循环中的时间复杂度 [英] Time complexity in loop

问题描述

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

Im new with algorithmic analysis. I just want to verify mi understanding:

例如：

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

显然共有1个赋值，n个比较，n个增量。

Is clear that there are 1 asignation, n comparations, and n incrementations.

n函数是：T（n）= t0 + t1 * n + t2 * n = t0 +（ t1 + t2）n = c0 + c1 * n

The n function is: T(n) = t0 + t1*n + t2*n = t0 + (t1+t2)n = c0+c1*n

所以复杂度为：O（n）

So the complexity is: O(n)

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

But, in this other cases i need some advice:

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

T（n）= t0 + t1 *（n + 1）+ t2 * （n + 1）???

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

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

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

T（n）= t0 + t1 *（n-1）+ t2 *（n-1）吗？

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

我想有人会说所有这些fors循环都只是O（n），那是唯一重要的事情。但是我想知道那些T（n）定义是否正确。

I think one would say all those fors loops are just O(n) and thats the only thing that matters. But i want to know if those T(n) definitions are ok.

推荐答案

是的，它们都是O（n），是的，您的 T 方程是正确的。

Yes, they are all O(n), and yes, your equations for T are correct.

通常，虽然 T 对于熟悉复杂性分析很有用，但在其他情况下不会使用。大多数人都担心问题的 O 。此外，一旦找到一组具有最小（或最佳） O 的算法，从该组中找到最佳算法的问题就很少取决于 T 。这是因为，例如，缓存一致性通常比大多数实际问题的绝对比较或添加次数更重要。

In general, while T is useful for getting familiar with complexity analysis, it's not used otherwise. Most people are concerned with the O of a problem. Furthermore, once you find a set of algorithms with minimal (or optimal) O, the problem of finding the best from that set rarely hinges on T. This is because things like, say, cache coherency usually matter way more than the absolute number of comparisons or additions for most practical problems.

如果您执行两个循环：

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

和

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

底部循环执行的时间比顶部循环执行的时间多（它将在 i == n 时执行，而顶层循环将跳过此操作）。因此，在计算运行时时，它们是不同的。前一个将精确地执行比较/递增 n 次（当 i 为 {时） 0,1，...，n-1} ）；底部将执行它 n + 1 （当 i 为 {0,1 ,.时。 ..，n-1，n} ）。

The bottom loop will execute one more time than the top one (it will execute when i == n, whereas the top loop will skip this). So when computing the run-time, these are different. The top-one will execute the comparison/increment n times exactly (when i is {0,1,...,n-1}) ; the bottom will execute it n+1 (when i is {0,1,...,n-1,n}).

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

However, in Big-O notation, you're looking for asymptotic behavior - i.e. what happens with n is really large. And in that case, you only take the factor of n that varies the fastest. When n is very large, the extra iteration of the loop above won't matter much at all, so both loops are O(n).

Big-O标记要记住的一件事是，它绝对不能捕获算法的所有内容。这是一个很好的首过检查- O（n）的算法几乎总是比 O（n ^ 3）。但是在具有相同（或几乎相同）指数的算法范围内，在实际系统上实现时，性能可能会大不相同。

One key thing to keep in mind with Big-O notation is that it most definitely does not capture everything about an algorithm. It's a good first-pass check - an algorithm that is O(n) is almost always going to be better than one that is O(n^3). But within the space of algorithms with the same - or almost the same - exponent, there can be wildly different performance when implemented on real systems.

这篇关于循环中的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！