c - 如何计算这个函数的复杂度？

Question

我想知道内部 for 循环的时间复杂度是多少，是 sqrt(n) 还是 log(n)？

void foo(int n)
{
 for (int i=0; i<n*n; ++i)
     for (int j=1; j*j<n; j*=2)
         printf("Hello there!\n");
}

标签： cloopsfor-loopcomplexity-theory

Answer 1

内部 for 循环中的 j 将取值 1,2,4,...2^t

同样根据给定的约束，2^2t = n

所以，t = (1/2)logn

因此内循环应该有时间复杂度 O(log(n))