循环中的时间复杂度

Question

我是算法分析的新手。我只是想验证一下我的理解：

例如：

for (i=0, i<n; i++) {
}

很明显，有 1 个指定、n 个比较和 n 个增量。

n 函数为：T(n) = t0 + t1*n + t2*n = t0 + (t1+t2)n = c0+c1*n

所以复杂度是：O(n)

但是，在其他情况下，我需要一些建议：

for (i=0, i<=n; i++) {
}

T(n) = t0 + t1*(n+1) + t2*(n+1) ???

for (i=0, i<n-1; i++) {
}

T(n) = t0 + t1*(n-1) + t2*(n-1) ???

for (i=1, i<n; i++) {
}

T(n) = t0 + t1*(n-1) + t2*(n-1) ???

我想有人会说所有这些 fors 循环只是 O(n)，这是唯一重要的事情。但我想知道那些 T(n) 定义是否合适。

Answer 1

是的，它们都是 O(n)，是的，你的方程T是正确的。

一般来说，虽然T对于熟悉复杂性分析很有用，但它不会用于其他方面。大多数人关心O的问题。此外，一旦您找到一组具有最小（或最优） 的算法，O从该集合中找到最佳的问题很少取决于T。这是因为对于大多数实际问题，例如缓存一致性之类的事情通常比比较或添加的绝对数量更重要。

如果你采取两个循环：

for (i = 0; i < n; i++) {}

和

for (i = 0; i <= n; i++) {}

底部循环将比顶部循环多执行一次（它将执行 when i == n，而顶部循环将跳过这一点）。所以在计算运行时间时，这些是不同的。top-one 将n准确地执行比较/递增时间 (when iis {0,1,...,n-1}) ; 底部将执行它n+1（何时i是{0,1,...,n-1,n}）。

但是，在 Big-O 表示法中，您正在寻找渐近行为- 即发生的事情n非常大。在这种情况下，您只需要考虑n变化最快的因素。当n非常大时，上面循环的额外迭代根本无关紧要，因此两个循环都是O(n).

使用 Big-O 表示法要记住的一个关键点是，它绝对不能捕获有关算法的所有内容。这是一个很好的第一遍检查 - 一个O(n)几乎总是比一个更好的算法O(n^3)。但是在具有相同（或几乎相同）指数的算法空间内，在实际系统上实现时可能会出现截然不同的性能。