algorithm - 嵌套循环运行时间？

Question

Big oh 符号中的运行时间是什么:

for(int i=1;i<N;i++)

    for(int j=1;j<N;j*=2)

当 j > N 时，循环将停止。如果我们让 k 为循环的任意迭代，则在第 k 次迭代中 j 的值将为 2k。当 2k > n 时循环停止，这发生在 k > log2 n 时。

因此，迭代次数仅为O(log n)，所以总复杂度为O(log n)。

这是正确的吗？

Answer 1

外循环的 O(n) 和内循环的 O(log(n))。所以总数是 O(n*log(n))。