使用3个嵌套循环的以下代码的时间复杂度

Question

有人可以解释下面这段代码的正确时间复杂性。

int sum,i,j,k,n;
sum = 0;
cin>>n;
int arr * = new int[n];
for (i=1;i<n;i=i*2){
   cin>>arr[i];
   for (j=0;j<n;++j)
       for (k=1;k<=n;k=k*2)
           sum+=arr[j];
}

Answer 1

三个for循环的边界似乎没有任何相互依赖性。因此，我们应该能够通过将三个循环的复杂性相乘来计算出整体运行时间。

i和k中的循环是O(lgN)，因为它们在每次迭代时将循环计数器加倍。 j的中间环是O(N)。这使得O(N*lgN*lgN)成为整体复杂性。