塊代碼的運行時間

Question

有人可以向我解釋爲什麼這段代碼的運行時複雜度T（n）爲2lgn + 2。我認爲它應該是lgn + 2。

public static reduce(int n){ 
int result = 0; 
while (n >1){ 
    n = n/2; 
    result = result +1; 
} 
return result; 
} 

Answer 1

大概假定每行都需要1個單位時間（不包括n > 1檢查）。

所以int result = 0;,n = n/2;,result = result +1;和return result;每個分類爲取1個單位時間。

2來自int result = 0;和return result;，每個執行一次。

2日誌Ñ來自n = n/2;和result = result +1;各自爲執行日誌 n次。

注：

n > 1也可分類爲產生3日誌 N + 2

n = n/2;和result = result +1;可以各自分類爲採取的時間2個單位導致的時間單位（同上）5日誌 n + 2.

這一切都很主觀。

唯一的全面協議將c日誌 n + d爲某些c和d。