給定函數的最壞情況時間複雜度是什麼？

Question

Void func(int n){ 
Int k=n; 
Int i=0; 
for(;i<n;i++){ 
while(k>1){ 
k>>=1; 
} 
} 

什麼是函數的最壞情況時間複雜度？也解釋解決方案。

Answer 1

在外循環的第一次迭代中，內循環運行log2(n)次。這是因爲k重複被2除（右移1），所以它的值成指數下降。

但是，對於外部循環的所有其他迭代，k的值仍小於1，因此內部循環不運行。

因此，時間複雜度由T(n) = Ө(n - 1) + Ө(log2(n)) = Ө(n)給出。