计算算法的时间复杂度

Question

可能的重复：
Big O 的简单英语解释

我已经做编程四年了，但我从来没有关注过时间复杂度到底是什么。我明天有一个面试，我知道他们会问我有关它的问题。任何人都可以帮助我通过示例简单地理解时间复杂度吗？通过查看代码，我们如何确定其复杂度是 O(n) 还是 O( log n) O(n) 等？

Answer 1

这是一个一般建议：

如果有一次迭代，并且迭代变量线性递增，那么它的复杂度为 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)

这只是手指交叉指南。一般来说，你必须有良好的概念才能推导出复杂性。这就是为什么他们被要求测试你的分析能力和概念。

Answer 2

您正在进入一个复杂的主题;-) 在大学里，您花了很长时间研究 O 表示法背后的理论。我总是倾向于归结为以下简化：

不包含任何循环的算法（例如：将文本写入控制台、从用户获取输入、将结果写入控制台）是 O(1)，无论有多少步骤。执行算法所需的“时间”是恒定的（这就是 O(1) 的含义），因为它不依赖于任何数据。

逐一迭代项目列表的算法的复杂度为 O(n)（n 是列表中项目的数量）。如果它在连续循环中迭代列表两次，它仍然是 O(n)，因为执行算法的时间仍然仅取决于项目的数量。

具有两个嵌套循环的算法，其中内部循环在某种程度上依赖于外部循环，属于 O(n^x) 类（取决于嵌套循环的数量）。

排序字段上的二分搜索算法属于 O(log(n)) 类，因为每一步项目数量都会减少一半。

上面的内容可能不是很精确，但这就是我试图记住一些重要价值观的方法。仅通过查看代码来确定复杂性并不总是那么容易。

对于进一步和更详细（和更正确）的阅读，大卫·赫弗南（David Heffernan）在他的评论中提到的问题似乎非常合适。