Algorithm(n):
i = 1 , k = 0
while i <= n {
for (j = 1 to n/i){
k = k 1
}
i = i * 2
}
我知道外回圈作業 logn，我不確定，但對于內回圈，它的作業方式類似于 n/i n/i/2 .. n/i/2^n 。（它沒有登錄，因為我們在外回圈中更新 i）
我不知道如何組合它們，因為內回圈的時間復雜度在每個回圈中都會發生變化。
誰能幫我解決這個問題？時間復雜度是多少
uj5u.com熱心網友回復：
實際上我對此做了一些數學運算，它給了我答案。
假設 n %2 = 0 并假設 2^x = n 并且 x 是 int。
對于 i = 1 -> n/i
對于 i = 2 -> n/2i
對于 i = 4 -> n/4i
對于 i = n -> n/ni
n/i ( 1 1/2 1/4 .. 1/n) 和 [1/2 1/4 ... 1/2^n] --> 1
n * 2/i --> n>i 所以答案是 O(n)
uj5u.com熱心網友回復：
外回圈中的變數i取值
i = 1, 2, 4, 8, ... X
其中X是2大于n(so X<= 2n) 的最小冪。
例如，當n = 32：
i = 1, 2, 4, 8, 16, 32, 64.
您的內部回圈運行n/i時間（這可能會向上或向下舍入，這在這里無關緊要）。
例如，當 時n = 32，內部回圈將運行：
32/1 32/2 32/4 32/8 32/16 32/32 32/64
=
32 16 8 4 2 1 0
= 63 times
如果將總和反轉，則得到2小于或等于的所有冪的總和n，即Theta(n)（最多2n）。
uj5u.com熱心網友回復：
答案是 O(n)。如果你開始檢查回圈，你會很容易得到它
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424331.html
標籤：算法
下一篇：如何對符合特定條件的串列進行分組