1

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

例如：

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) 定义是否可以。

4

2 回答 2

5

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

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

如果你采取两个循环：

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

和

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

底部循环将比顶部循环多执行一次（它将执行 when i == n，而顶部循环将跳过此）。所以在计算运行时时，这些是不同的。前一个将准确执行比较/增量n时间（何时i）{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). 但是在具有相同（或几乎相同）指数的算法空间内，在实际系统上实现时可能会有截然不同的性能。

于 2013-08-26T17:22:03.870 回答
2

O(n) 表示有常数 M>0 表示运算次数 < M*n。

所以在你的情况下，第二种情况是 O(n)，我们可以说它是 O(n-1) 但更容易说它是 O(n) 因为它在 n -> 时完全相同无穷。

n-1/n -> 1

如果 T(n) 是操作的确切数量，因此您无法简化结果

于 2013-08-26T16:36:58.130 回答