c数据结构时间复杂度求解问题

Question

我想确保这是正确的答案。答案：

T(n) = (n log n +1 ) 
big 0 = O(n log n)

sum = 0;      ---- 1
for( i=1; i<=n ; i*=2) ---- log n ? 
for(j=1; j<=n ; j++) --- n 
sum++; ----1

Answer 1

1. 外循环的迭代次数是n中最高有效位的索引。因此，它确实是层(log₂(n((

2. 内部循环的迭代次数恰好是n。

然后，内部循环的主体的总迭代次数为n*floor(log₂(n((，测试、增量和主体都在恒定时间内执行。

因此，该代码的时间复杂度为O(n.log(n((