查找嵌套循环的时间复杂度

Question

对于下面的循环，

int sum = 0;
for (int i = 1; i < N; i *= 2)
    for (int j = 0; j < N; j++)
        sum++;

时间复杂度是多少，我应该怎么想？我的猜测是外循环总共运行 log(N)。内部循环运行 N 次。所以时间复杂度应该是Nlog(N).

我说得对吗？

提前致谢。

Answer 1

对于第一个循环，迭代次数等于log2(N)，因为i每次迭代都会加倍。

对于第一个循环的每次迭代，第二个循环运行 N 次。

因此总体时间复杂度=(log2(N) * N)，其中函数log2(x)=log(x)以2为底。