algorithm - 循环时间复杂度

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) ???

我认为有人会说所有这些 for 循环只是 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++) {}

底部循环将比顶部循环多执行一次(它将在 i == n 时执行，而顶部循环将跳过此循环)。所以在计算运行时时，这些是不同的。 top-one 将执行比较/递增 n 次(当 i 为 {0,1,...,n-1});底部将执行它 n+1(当 i 为 {0,1,...,n-1,n} 时)。

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

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