无法找到 Big(O) 时间复杂度。

Question

以下代码的时间复杂度是什么：

什么是时间复杂度：

int count = 0;
for (int i = N; i > 0; i /= 2) {
     for (int j = 0; j < i; j++) {
          count += 1;
     }
}

这是O(n)还是O(log(n)*n)的时间复杂度？

- Anurag Yadav

Answer 1

我认为这种类型的问题在过去的帖子中已经得到了回答。我将介绍这个问题的基本前提。 假设N = 8。

First Loop (i)    No. Of Second Loop Runs 
8                 8
8/2               8/2
8/4               8/4
8/8               8/8

推算和总结第二个循环将针对上述过程运行的次数:

N + (N / 2) + (N / 4) + ... + 1

我们需要解决以上一系列问题以得到总的时间复杂度。我们来看一个这个系列是无穷大（非常大）的情况。在这种情况下，这种求和的公式为：

a + (a / r) + ... = a / (1 - r), where a is first term and r is common ratio

那么，结果将是：

N + (N / 2) + (N / 4) + ... = N / (1 - (1/2)) = (2 * N)

这是序列求和的最大（上限）值。2是一个常数项。因此，我们可以得出最坏情况下的时间复杂度为O(N)。

- Rahul

Answer 2

内部循环执行i-1次。初始时，i=n，每次迭代i=n/(2^k)。

因此，在第一次迭代中，内部循环运行n次。下一次迭代，内部循环运行n/2次，最后一次迭代中，内部循环只运行一次。因此，你可以将其写成一个序列：

假设T(n)是你的代码的时间复杂度，则

T(n)=n+ n/2 + n/4 + ... + 1=O(n)

- Jut

Answer 3

为了验证Rahul的推导，您可以运行以下C#脚本来查看对于提供的任何N值，count会增加接近2N次。

int[] ns = { 10, 100, 1000, 10000, 100000 };

foreach (int N in ns)
{
    int count = 0;
    for (int i = N; i > 0; i /= 2)
    {
        for (int j = 0; j < i; j++)
        {
            count += 1;
        }
    }

    Console.WriteLine("N: " + N);
    Console.WriteLine("count: " + count);
}

当你试图通过数学方法解决算法的大O复杂度问题，或者仅仅是为了证明你的推导是正确的时，使用几个小的N值进行测试是估计算法规模的好方法。

- Bill the Lizard

Answer 4

外部循环总共运行log(n)次。看内部循环。第一次，内部循环运行n次，第二次运行n/2次，以此类推，因此得到以下系列：

n(1 + 1/2 + 1/4 + 1/8 + ...)

这个的总和等于2*n，这意味着它是O(n)。

因此，由于外部循环运行O(logn)次，内部循环运行O(n)次，时间复杂度为O(n)。

由于内部循环不需要n步，所以它不是O(nlogn)。

事实上，所有步骤的总和是O(n)。

- Ali

---

@t.niese 因为计数器被反复除以2。 - Alex Reinking

Answer 5

这里所有的答案都很有用。我想讨论一些基本的东西。我假设你对列表中的一个或多个条目没有清楚的概念，这就是导致你对此问题感到困惑的原因。

现在，在所有答案中，他们都考虑了最内部的表达式？你应该问自己“为什么？”因为这会让你下次解决这些问题。问题在于，程序运行或完成所需的时间取决于硬件和许多其他因素。长话短说，如果直接使用执行时间，那么它是无法比较的。也许你的机器比我的快，等等。

这就是为什么我们开始识别算法重复执行的基本操作。如何确定这些基本操作。通常情况下，这些操作是执行最频繁的操作，无论何时执行，执行此操作所需的时间都是恒定的。最内部的表达式被执行得最频繁。所以这就是为什么他们要考虑它的原因。

你可能会问，有些for循环的比较也像这样（尤其是第二个for循环操作）。我们应该将它视为基本操作吗？答案是“是”，但它不会改变任何东西。它只会向最内部的表达式添加一个恒定的偏移量，使最终复杂度相同。只需将最内部表达式视为单位时间基本操作，即可考虑最重要的事情。请注意，这并不是按时间单位计算 - 我们只是在计算它被执行的次数。

在此之后，分析就变得更容易了。你必须告诉我，在长度为n的数组中，最内部的表达式被执行了多少次。这就是其他答案中正在做的事情。希望它能澄清一些事情。

- user2736738

Answer 6

在第一次迭代中，i=N，因此分配给j的不同值的数量为N。在第二次迭代中，i=N/2，在第三次迭代中，i=N/4，以此类推。因此，程序的总成本大约为N + N/2 + N/4 + ...，最多为2N。因此，算法的时间复杂度为O(N)。请注意，求和中的项数是分配给i的不同值的数量，大约为log N。但是这些项按几何级数递减，因此总和的总成本由第一项主导。说这个求和有log N个项，每个项最多为N，因此总成本为O(N log N)并不是错误的。只是这种分析比较粗略，得到的上限O(N log N)并不紧密。

- Ashwin Ganesan