大O表示法for循环

Question

如何找到大O表示法本作环行代码

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

有谁知道？

我读了一些关于Big O Notation的文章，这是一个非常令人困惑的话题。我知道这通常是这样的循环→for (int n = 0; n < 20; ++n)，有一个大O表示法O（1），随着输入增加13，输出也增加，线性复杂。这与上述情况相同吗？

Answer 1

甲环是这样的：

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

迭代Ñ倍，因此，如果有doSomething O（1）运行时间，则循环作为一个整体具有O（Ñ）运行时间。

类似地，这样的循环：

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

迭代⌈√Ñ⌉倍，因此，如果有doSomething O（1）运行时间，则循环作为一个整体具有O（√Ñ）运行时间。

顺便说一句，请注意，虽然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); 
}