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

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)。

我对么？

提前致谢。

标签： algorithmtime-complexitybig-o

Answer 1

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

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

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