与えられた関数の最悪の時間の複雑さは何ですか？

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)で与えられます。