我不明白這段代碼將如何產生O(log n)的復雜性。回圈內的陳述句將作業多少次？
int a = 0, i = N;
while (i > 0) {
a = i;
i /= 2;
}
uj5u.com熱心網友回復：
設N=16，迭代次數為
i | loop
--------
16 | 1
8 | 2
4 | 3
2 | 4
1 | 5
你可以看到log 2 (16) = 4，迭代次數是 log 2 (16) 1。或者你可以為它創建一個公式 f(N) = F(N/2) 1。假設我們有N = 2^K 所以我們有：
F(N) = F(N/2) 1
F(N) = F(N/4) 1 1
F(N) = F(N/8) 1 1 1 = F(N/(2^3)) 3
...
...
...
F(N) = F(N/2^K) K => F(2^K/2^K) K => F(1) K => 1 K
所以如果N = 2 K那么 K = log 2 (N)
uj5u.com熱心網友回復：
回圈的迭代次數是有效位的數量，N因為i在每次迭代結束時減半。因此，回圈迭代log 2 (N)次 for N>0，否則不迭代。每次迭代都有 3 個簡單的操作，加法、除法和測驗，因此時間復雜度為O(log(N))。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420159.html
標籤：