algorithm - 运行时间是 o(logn) 还是 o(n)？

Question

我对这个问题有些困惑。似乎每走一步，问题的规模就会减少一半，这表明 O(logn)。但如果你真的仔细想想，交互次数只是几何级数 2 + 4 + 8 + ... 小于 n，这表明 O(n)。有人可以提供他们的见解吗？

for (int i=1; i < n; i=2i)
    for (int j=i; j < n; j++)
        // do something

Answer 1

复杂度为O(n log n)

首先是为了获得更多许可，例如:当 n 为 4 时，外循环迭代 2 次当 n 为 64 时，ouret 循环迭代 6 次所以外层循环迭代 log2(n) 次。

解决方法:在外循环的第一次迭代中，“do somethings”语句运行了 n 次在外循环的第二次迭代中，“do somethings”语句运行 n-2 次在外循环的最后一次迭代中，“do somethings”语句运行了 n-log2(n) 次

因此对于整个程序的执行，“做某事”语句运行了 n+n-2+n-4+...+n-log2(n) 次。它等于 n*log2(n)-(1+2+4+8+...+log2(n)) = n*log2(n)-(2n-1) 次。所以复杂度是o(n log n)