最差的時間複雜度（大O）for循環

Question

所以我理解大多數複雜性問題;然而，這讓我感到困惑。

當for循環中的第二條語句如下（i * i < n）時，對於循環來說，Big Big O會是什麼？它將如何計算？

for (i = 1 ; i * i < n ; i++) 

Answer 1

假設n是輸入的大小的代理（和您的代碼將只對輸入的每個加工的構件執行循環體一次，並且不存在其他輸入元件選擇器邏輯）。

i * i < n 
    i^2 < n 
    i < Sqrt(n) 

所以，時間複雜度爲O(Floor(Sqrt(n)))。

讓我們來看一個例子與n = 10（該表顯示了變量的狀態在每次迭代結束時，此刻i++評估準確之前和進行i * i < n檢驗）。

Iteration, i, i * i, n 
     1, 1,  1, 10 
     2, 2,  4, 10 
     3, 3,  9, 10 
     4, 4,  16, 10 -- 16 > 10, abort loop 
     5, 5,  25, 10 -- for illustrative purposes 

（注意，作爲i^2 < 10檢查之前執行執行循環，迭代4將不會被執行，因此該循環將被執行3次。10精確平方根是3.1622...但迭代計數是基於0的自然數，所以使用Floor。）。

Answer 2

i*i<n 

可以轉化爲

i<sqrt(n) 

因此其實際上可以O(sqrt(n))

*如何*`* I