min*_*ree 8 algorithm complexity-theory
可能重复:
Big O的简单英文解释
我现在已经做了4年的编程,但我从未关注过时间复杂性.我明天接受采访,我知道他们会问我关于它的问题.任何人都可以通过简单的方式帮助我理解时间复杂性吗？通过查看代码,我们如何判断它的复杂性是O(n)还是O( log n)O(n)等？
Sha*_*fiz 19
以下是一般性建议:
如果存在单次迭代,并且迭代变量线性递增则其为O(n),例如
for(i=0;i<n;i++) //O(n)
for(i=0;i<n;i = i + 4) // still O(n)
如果迭代变量在几何上递增,那么它是O(log n)
例如
for(i=1;i<n;i = i * 2) //O(log n)
注意,实现不必使用循环,它们可以使用递归来实现.
如果存在嵌套循环,其中一个复杂度为O(n)而另一个复杂度为O(logn),那么整体复杂度为O(nlogn);
例如
for(i=0;i<n;i++) // O(n)
for(j=1;j<n;j=j*3) // O(log n)
//Overall O(nlogn)
这只是一个手指交叉指南.通常,您必须有一个好的概念来推导复杂性.这就是他们被要求测试你的分析能力和概念的原因.
Tho*_*mar 10
你在这里进入一个复杂的话题;-)在大学里,你花了很多时间在O符号背后的理论上.我总是倾向于采用以下简化方式:
不包含任何循环的算法(例如:将文本写入控制台,从用户获取输入,将结果写入控制台)为O(1),无论步数多少.执行算法所需的"时间"是恒定的(这是O(1)的意思),因为它不依赖于任何数据.
逐个遍历项目列表的算法具有复杂度O(n)(n是列表中的项目数).如果它在连续循环中通过列表迭代两次,它仍然是O(n),因为执行算法的时间仍然仅取决于项目的数量.
具有两个嵌套循环的算法,其中内部循环以某种方式依赖于外部循环,在O(n ^ x)类中(取决于嵌套循环的数量).
排序字段上的二进制搜索算法在O(log(n))类中,因为每个步骤中项目数减少一半.
以上可能不是很精确,但这就是我试图记住一些重要价值观的方法.从查看代码来看,确定复杂性并不总是那么容易.
为了进一步和更详细(和更正确)的阅读,David Heffernan在他的评论中提到的问题似乎非常合适.