Big-O嵌套while循環

Question

i <-- 1 
while(i < n) 
    j <--1 
    while(j < i) 
     j <-- j * 2 
    i <-- i + 1 
done 

我在這裏拍攝的內容是O(log n)。我猜外環是O(n)，整體複雜度爲O(n log n)。確認？

Answer 1

是的，你是對的，但它不是那麼簡單，正確地弄清楚:)。

內環是微不足道的log n，沒有必要進一步解釋。

但是，外循環並不那麼簡單，因爲在每個循環中它會改變內循環執行的時間。

如果你想想看，內循環將被用於（爲i增加）運行：

log 1 + log 2 + log 3 + log 4 + log 5 .... + log n 

到logharitms的一些規律。由於，這是一樣的log (1*2*3*4*....*n)是相同

log (n!)

有一個法律，n!具有相同的複雜性（注意，這是複雜，它不是在代數相同）n^n

因此log (n!) = O(log (n^n))

現在我們只需切換到代數，因爲log (n^k) = k*log (n)我們得到的結果

log (n^n) = n log n

結果：

時間複雜度爲O(n log n)

Answer 2

呦你可以用Sigma符號一步一步地正式進行，以獲得確切的迭代次數 - 查看Discrete Loops and Worst Case Performance論文（第10頁）。

結果已經被經驗證實。