计算算法的时间复杂度
可能重复：
Big O的纯英文解释
现在我已经做了4年的编程，但我从未关注时间复杂性。 我明天有一个采访，我知道他们会问我关于它的问题。任何人都可以用简单的术语来帮助我理解时间复杂性吗？通过查看代码，我们如何确定它的复杂度是O（n）还是O（日志n）O（n）等？
这是一个一般性建议：
如果只有一次迭代，并且迭代变量线性递增，那么它就是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)
这只是一个手指交叉准则。 一般来说，你必须有一个好的概念来推导复杂性。 这就是为什么他们被问及为什么要测试你的分析能力和概念。
你在这里变成一个复杂的话题;-)在大学里，你花了很多年的时间研究O标记背后的理论。 我总是倾向于下面的简化：
不包含多少步骤的算法不包含任何循环（例如：将文本写入控制台，从用户获取输入，将结果写入控制台）为O（1）。 执行该算法所需的“时间”是恒定的（这是O（1）的含义），因为它不依赖于任何数据。
一个逐一遍历项目列表的算法具有复杂度O（n）（n是列表中项目的数量）。 如果它在连续循环中遍历列表两次，它仍然是O（n），因为执行算法的时间仍然取决于项目的数量。
一个带有两个嵌套循环的算法，其内部循环以某种方式依赖于外部循环，位于O（n ^ x）类中（取决于嵌套循环的数量）。
在排序字段中的二分搜索算法在O（log（n））类中，因为在每一步中项目的数量减少了一半。
以上可能不是很精确，但这是我试图记住一些重要价值的方式。 从查看代码，确定复杂性并非总是那么容易。
为了进一步和更详细（更正确）的阅读，David Heffernan在他的评论中提到的问题似乎很合适。
链接地址: http://www.djcxy.com/p/6747.html