For 循环的大 O 表示法

Question

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

\n\n

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

\n\n

有人知道吗？

\n\n

我读过一些关于大 O 表示法的内容，它\xe2\x80\x99 是一个非常难以理解的主题。我知道通常像这样的 for 循环 \xe2\x86\x92 for (int n = 0; n < 20; ++n)，有一个大 O 表示法O(1)，随着输入增加 13，其输出也增加 13，具有线性复杂度。是不是和上面的情况一样呢？

\n

Answer 1

像这样的循环：

\n\n

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

\n\n

迭代n次，因此如果doSomething运行时间为 O(1)，则整个循环的运行时间为 O( n )。

\n\n

同样，像这样的循环：

\n\n

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

\n\n

迭代 \xe2\x8c\x88\xe2\x88\x9a n \xe2\x8c\x89 次，因此如果doSomething运行时间为 O(1)，则整个循环的运行时间为 O(\xe2\x88\x9a n )时间。

\n\n

顺便说一句，请注意，尽管pow(j, 2)运行时间为 O(1)，因此它不会影响循环的渐近复杂性，但它仍然相当慢，因为它涉及对数和指数运算。对于大多数目的，我建议这样做：

\n\n

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

\n\n

或者也许是这个：

\n\n

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

\n