大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); 
}