嵌套循环 运行 时间？

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