while循環的大O

Question

我在這裏有一些代碼，其中x增長像大O（n），但我不知道爲什麼。它似乎更像是一個對數大O.我能找到一些幫助來找出它爲什麼會像大O（n）一樣增長嗎？謝謝！

 i = k; x = 1.0; 
    while (i > 1) { 
    i = (int) Math.floor(i/2.0); 
    x = x *2 ; 

Answer 1

複雜性分析有一點做與一個變量是什麼值結束了，它的算法的性能，簡單地（時間複雜度）有多少步驟需要做基於一些輸入值。

在這種情況下，給定的輸入值k，你的複雜性是O(log N)因爲由兩個分割「半部剩餘的溶液空間」上的每個迭代中，沿着線：

i = 128 64 32 16 8 4 2 1 

的生長變量x，如上所述，它與算法的複雜性無關，每次都通過循環加倍。

所以，你有一個循環由每次迭代減半的值控制。並且您有在每次迭代加倍一個變量：

i = 128 64 32 16 8 4 2 1 
x = 1 2 4 8 16 32 64 128 

因此是有意義的輸入值和最終變量值之間的關係將是線性的，如圖由等效Python代碼：

ctrl = 1024 
other = 1 
while ctrl > 0: 
    print('{0:4d} {1:4d}'.format(ctrl, other)) 
    ctrl = ctrl // 2 
    other = other * 2 

，輸出：

1024 1 
512 2 
256 4 
128 8 
    64 16 
    32 32 
    16 64 
    8 128 
    4 256 
    2 512 
    1 1024 

注意那裏，儘管在other終值是1024，只有十 「臺階」 WER因爲log21024是10。

Answer 2

如果你正在尋找最優化的問題，它看起來像你只是在計算最大位

這也可以多一點有效地實現與Integer.highestOneBit(int i)

其定義爲

public static int highestOneBit(int i) { 
    // HD, Figure 3-1 
    i |= (i >> 1); 
    i |= (i >> 2); 
    i |= (i >> 4); 
    i |= (i >> 8); 
    i |= (i >> 16); 
    return i - (i >>> 1); 
} 

，並應在一定的時間在運行（O（1）），因爲它是唯一的位運營商

通過移位它是如何工作的比特下降或與自己進行或運算，導致過去最大的所有比特變爲1，然後隔離其最大值，減去該數字後移動以除去所有後續1s