我的問題是關于找到這個演算法的復雜性。J值與n有關，所以我對此感到困惑。
這個偽代碼的漸近復雜度是多少？
for i=1 to n
do
j = 1;
while (j < n)
do
j = j * 2;
謝謝。
uj5u.com熱心網友回復：
我相信它是O(n log2n)
外部回圈稱為n時間，內部回圈稱為時間，因為在每次迭代中，都加倍。對于第一次迭代，即；等于并繼續，直到log2njk=0j12, 4, 8, ...2k>=n
uj5u.com熱心網友回復：
如果我在內回圈的末尾添加一個列印，我會看到：
(1,2,5)
(1,4,5)
(1,8,5)
(2,2,5)
(2,4,5)
(2,8,5)
(3,2,5)
(3,4,5)
(3,8,5)
(4,2,5)
(4,4,5)
(4,8,5)
(5,2,5)
(5,4,5)
(5,8,5)
所以它看起來是 O(n^2) 但內部回圈看起來是恒定的，所以可能是 O(n) - 如果(j < n)部分切換到(j < i)，那將更接近 O(n log(n))：
(2,2,5)
(3,2,5)
(3,4,5)
(4,2,5)
(4,4,5)
(5,2,5)
(5,4,5)
(5,8,5)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463764.html