time - N+N/2+N/4...迭代运行时间

Question

我正在查看一个循环访问大小为 N 的数组的代码示例。

• 第一次迭代，我将遍历所有元素 -> N
• 下一次迭代，我只遍历数组的一半 -> N/2
• ...

这一直持续到我必须经过的数组的大小达到 1。

这个运行时间会是 O(N) 吗？还是 O(NlogN)？

我以为会是O(NlogN)，但是书上说只有O(N)。

Answer 1

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3};

  for (unsigned n(v.size()); n; n /= 2)
  {
    for (unsigned i(0); i < n; ++i)
      std::cout << v[i];

    std::cout << std::endl;
  }
}

这个程序在每行打印 π 的一部分(第一行 n 数字，...，最后一行 1 数字):

3141592653589793

31415926

3141

31

3

它打印的总位数是 31 = v.size() * 2 - 1 .

一般来说，给定一个大小为 N 的向量(N = 2^k)，执行内部指令(std::cout << v[i])2N - 1次 ( O(N) ):

N + N/2 + N/4 + ... + 2 + 1 = 2N - 1

如果N不是二的幂，您必须对公式进行一些小的调整，但复杂度保持不变。