我更喜欢尽可能少的正式定义和简单的数学。
当前回答
算法例(Java):
public boolean search(/* for */Integer K,/* in */List</* of */Integer> L)
{
for(/* each */Integer i:/* in */L)
{
if(i == K)
{
return true;
}
}
return false;
}
算法描述:
这个算法搜索一个列表,项目按项目,寻找一个密钥,在列表中的每个项目,如果它是密钥,然后返回真实,如果循环没有找到密钥,返回虚假。
Big-O 评分代表了复杂性(时间、空间等)的顶端。
要找到 The Big-O on Time Complexity:
计算时间(考虑到输入大小)最糟糕的案例需要: 最糟糕的案例: 关键不在列表中 时间(Worst-Case) = 4n+1 时间: O(4n+1) = O(n) <unk>在大O,恒例被忽视 O(n) ~ 线性
还有大欧米加,它代表了最佳案例的复杂性:
最佳案例:关键是第一个项目 时间(最佳案例) = 4 时间: Ω(4) = O(1) ~ Instant\Constant
其他回答
大 O 评级是描述算法将运行多快的方式,因为有意数量的输入参数,我们将称之为“n”。在计算机科学中是有用的,因为不同的机器以不同的速度运行,简单地说算法需要 5 秒,不会告诉你很多,因为虽然你可能运行一个系统与 4.5 GHz 八核处理器,我可能运行一个系统。
大 O 描述一类功能。
它描述了大输入值的快速功能的增长方式。
对于一个特定的函数f,O(f)分解了所有函数g(n),您可以找到一个n0和一个恒定的c,以便与n>=n0的g(n)的所有值都低于或相当于c*f(n)。
在较少的数学词语中,O(f)是一组函数,即所有函数,从某些值 n0 向前,增长缓慢或像 f 一样快。
如果 f(n) = n 那么
g(n) = 3n 是 O(f) 。 因为恒定的因素不重要 h(n) = n+1000 是 O(f) 因为它可能比所有值小于 1000 但对于大 O 只有大输入物质。
然而,i(n) = n^2不在O(f)中,因为一个四方函数比一个线性函数增长得更快。
这里来了大O,告诉我们这个数学是多么艰难。
现在他们要求我添加一个到十个!为什么我会这样做?我不想添加一个到六个?添加一个到十个......好......这会更难!
对于大 n 而言, n 平方比 n 更大。
一个:我选择一张卡在我们现在工作的地板部分,你可以为我选择一个,如果你愿意(第一次我们这样做,“我们现在工作的地板部分”是整个地板,当然。
大 O 告诉我们:这个类型需要 O(n log n) 工作完成,在中间情况下。
现在你知道我的朋友,大O,他帮助我们做不到工作,如果你知道大O,你也可以做不到工作!
你和我一起学到了这一切!你太聪明了!谢谢你!
现在这个工作已经完成了,让我们玩吧!
大 O 在平式英语是如<=(少于或等)。当我们说为两个函数f 和 g,f = O(g) 它意味着f <= g。
但是,这并不意味着任何 n f(n) <= g(n) 事实上,它意味着 f 是增长方面低于或等于 g 的,这意味着在一个点 f(n) <= c*g(n) 之后,如果 c 是恒定的,然后一个点意味着所有 n >= n0 在那里 n0 是另一个恒定的。
告诉你从亚马逊订购哈利·波特:完整的8电影收藏(Blu-ray)并同时在线下载相同的电影收藏。你想测试哪种方法更快。
从实验中,我们知道在线购物的规模比在线下载更好,很重要的是要了解大O评级,因为它有助于分析算法的规模性和效率。
注意: 大 O 评级是算法最糟糕的场景,假设 O(1) 和 O(n) 是上面的例子最糟糕的场景。
参考: http://carlcheo.com/compsci
推荐文章
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 给定一个数字,找出下一个与原始数字具有完全相同的数字集的更高的数字
- HSL到RGB的颜色转换
- 使用Java在原语数组中查找最大/最小值
- 好的Java图算法库?
- foreach和map有区别吗?
- 什么时候我应该使用Kruskal而不是Prim(反之亦然)?
- 取一个集中在中心的随机数
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下,您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何使用JavaScript比较软件版本号?数量(只)
- 在常数平摊时间O(1)中将一个对象追加到R中的列表?
- 跳跃表vs.二叉搜索树