我在弄清幾個小的代碼片段的時間方程時遇到了麻煩。
int sum = 0;
for (int k =n; k > 0; k /= 2)
for (int i = 0; i < k; i )
sum 。
int sum = 0;
for (int i = 1; i < n; i *=2)
for (int j = 0; j < i; j )
sum 。
int sum = 0;
for (int i = 1; i < n; i *=2)
for (int j = 0; j < n; j )
sum 。
如你所見，它們都非常相似。我不是在尋找一個確切的答案，我只是不確定該從哪里開始處理內回圈。看起來它們都會運行n次，但它們不可能都是一樣的，對嗎？我很確定所有的外回圈都是log(n)，sum 只是一個常數(1)，但我不太確定所有的內回圈有什么不同，以及這將如何改變方程式。
uj5u.com熱心網友回復：
第三個代碼片斷是最容易分析的。對于每個外回圈迭代，內回圈將進行'n'次迭代。由于外回圈的迭代次數是O(log(n))，所以總的迭代次數（以及第三個代碼段的復雜性）是O(n*log(n))。
前兩個代碼片段具有相同的復雜性，只是外回圈在第一個片段中以降序迭代，而在第二個片段中以升序迭代。所以你遍歷所有小于'n'的2的冪，然后重復內回圈的相應次數。迭代的總次數為
。1 2 4 ... 2^k
其中k=log2(n)。2的冪的總和是2^(k 1)=2*2^k=2*n。所以，這兩種情況下的復雜度都是O(n)。
uj5u.com熱心網友回復：
int sum = 0;
for (int k =n; k > 0; k /= 2)
for (int i = 0; i < k; i )
sum 。
n n/2 n/4 n/8 ... 1 ≈ 2n = Θ(n)
int sum = 0;
for (int i = 1; i < n; i *=2)
for (int j = 0; j < i; j )
sum 。
1 ... n/8 n/4 n/2 n ≈ 2n = Θ(n)
。
(好吧，不是完全以n、n/2等結束，而是在這些的2倍之內，所以對于復雜度等級來說并不重要。)
int sum = 0;
for (int i = 1; i < n; i *=2)
for (int j = 0; j < n; j )
sum 。
n n ... n ≈ log(n) × n = Θ(n log n)
。轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/325794.html
標籤：