For 循环的大 O 表示法

Question

如何找到此 for 循环代码行的大 O 表示法

for (int j = 0; pow(j,2) < n; j++) ?

有人知道吗？

我读了一些大 O 表示法，这是一个非常难以理解的话题。我知道通常像这样的 for-loop → for (int n = 0; n < 20; ++n)，有一个大 O 符号 O(1)，随着输入增加 13，它的输出也增加，线性复杂。是不是和上面一样的情况？

Answer 1

像这样的循环：

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

迭代 n 次，所以如果 doSomething 有 O(1) 运行次，那么整个循环有 O(n) 运行次.

类似这样的循环：

for (int j = 0; pow(j, 2) < n; j++) {
    doSomething(j);
}

迭代 ⌈√n⌉ 次，所以如果 doSomething 有 O(1) 运行时间，那么整个循环有 O( √n)运行次.

顺便说一下，请注意虽然 pow(j, 2) 是 O(1) 运行时间——所以它不会影响你的循环的渐近复杂度——它仍然很慢，因为它涉及对数和求幂。对于大多数用途，我建议改为：

for (int j = 0; j * j < n; j++) {
    doSomething(j);
}

或者这个：

for (int j = 0; 1.0 * j * j < n; j++) {
    doSomething(j);
}

Big O Notation for a For-Loop