算法的大O表示法

Question

我正在忙于一项任务，但有一个问题困扰着我。我知道不应该直接问作业问题，所以如果我没有得到明确的答案，我也理解。但是还是想问一下。

我们需要计算不同算法的运行时间复杂度，我卡在了这个上面。

for(int i = 1 ; i < n ; i++)
    for(int j = 0 ; j < i ; j +=2)
        sum++;

根据我的理解，我认为时间复杂度应该低于O(n²)，因为嵌套循环没有完全运行n次，而且j变量在每次循环中增加2，而不是像普通for循环一样迭代。然而，当我对N=10、N=100、N=1000等进行了一些代码模拟时，输出sum变量时我得到了以下结果。

N = 10 : 25, 
N = 100 : 2500,
N = 1000 : 250000,
N = 10000 : 25000000

当我看到这些结果时，O符号似乎应该比O(n)大得多。

在这个任务中，我们被给予了4个选项：O(1)，O(n²)，O(n)和O(logn)。就像我先前所说的，我无法理解它为什么会像O(n²)那样大，但是结果指向那里。所以我认为我没有完全理解这个问题，或者我错过了一些关键点。

任何帮助都将不胜感激！

- Nick Corin

---

"j变量在每个循环中都会翻倍。" 我认为你误读了它。j*=2是翻倍；j+=2是增加两个。 - Kevin

是的，抱歉，那是一个打错的字 :) 我现在会将其编辑掉。 - Nick Corin

它介于O(n)和O(n^2)之间，所以我认为它默认选择较大的那个。 - Chemistpp

提示：1+2+...+n的总和是多少？省略每隔一个数的项会如何影响这个总和？ - user395760

1+2+3+...+N = (N+1)*N/2 -> O(N^2) - Jarod42

@Chemistpp 3n * ln n 也介于线性和二次之间，尽管在技术上它属于 O(n^2)，但这不是一个紧密的边界（通常我们谈论的是紧密的边界）。它是 O(n log n) 的。 - user395760

Answer 1

大O符号并不给出操作次数，它只告诉你随着输入增加它会有多快的增长。这就是你观察到的。

当你将输入增加c倍时，总操作次数增长c^2倍。

如果你精确地计算(几乎)确切的操作次数，你会得到(n^2)/4。

当然你可以用求和来计算，但由于我不知道在SO上如何使用数学公式，所以我将给出一个"经验主义"的解释。同样的循环内嵌循环，具有相同的起始和结束条件，产生的结果是n^2。这样的循环产生了所有可能的组合矩阵，对于"i"和"j"。所以如果起始值为1，结束值为N，那么两种情况下你都会得到N*N个组合（或有效迭代次数）。

然而，你的内部循环是针对i < j的。这基本上将这个正方形变成了一个三角形，即第一个0.5因子，然后你跳过每个其他元素，这是另一个0.5因子；相乘得到1/4。

O(0.25 * n^2) = O(n^2)。有时人们喜欢保留这个因子，因为它可以让你比较两个具有相同复杂度的算法。但这并不改变相对于n的增长率。

- luk32

---

感谢您在这里如此清晰地解释。 - Nick Corin

那里的1/4解释得非常好。 - molbdnilo

Answer 2

请记住，大O符号是渐进符号。常数（加法或乘法）对其没有任何影响。

因此，外部循环运行n次，在第i次上，内部循环运行i/2次。如果没有“/ 2”部分，它将是所有数字1 .. n的总和，这是众所周知的n *（n + 1）/ 2。它扩展为a * n ^ 2 + b * n + c，其中a非零，因此它是O（n ^ 2）。

我们不是在求和n个数字，而是在求和n/2个数字。但是，这仍然大约是（n/2）*（（n/2）+1）/ 2。这仍然扩展为d * n ^ 2 + e * n + f，其中d非零，因此仍然是O（n ^ 2）。

- Angew is no longer proud of SO

Answer 3

从您的输出看，似乎：sum ~= (n^2)/4。

显然，这是O(n^2)（实际上可以用teta替换O）。 您应该回忆一下大O符号的定义。请参见http://en.wikipedia.org/wiki/Big_O_notation。

- Gari BN

Answer 4

事实上，这里的操作次数取决于平方数n，即使总数小于n²。然而，缩放对于大O符号来说是最重要的，因此它是O(n²)。

- Matz

---

这里的“dependent on”仅意味着“与...成比例”。实际数字也取决于n（通过某些c的函数f(x)=cx²），但它不属于O(n)。 - user395760

这对我有意义，谢谢。我一直认为它应该是准确的，并且在某种程度上Big-O应该是“最小”的。 - Nick Corin

Answer 5

使用：

for (int i = 1 ; i < n ; i++)
    for (int j = 0 ; j < i ; j +=2)
        sum++;

我们有：

0+2+4+6+...+2N == 2 * (0+1+2+3+...+N) == 2 * (N * (N+1) / 2) == N * (N+1)

因此，当 n == 2N 时，我们有 (n / 2) * (n / 2 + 1) 约等于 (n * n) / 4

因此，O(n²)

- Jarod42

Answer 6

关于时间复杂度，你的理解是不准确的。时间复杂度不仅与“sum”变量相关。“sum”仅计算内循环迭代的次数，但你还必须考虑外部循环迭代的总次数。

现在考虑一下你的程序：

 for(int i = 1 ; i < n ; i++)
    for(int j = 0 ; j < i ; j +=2)
        sum++;

时间复杂度是指程序运行时间与输入值（这里是n）的关系。这里的运行时间并不是指在计算机上执行程序所需要的实际时间，实际所需时间因计算机而异。因此为了获得机器无关的运行时间，大O符号非常有用。大O符号来自数学，它以数学函数的形式描述了运行时间。

外层循环总共执行(n-1)次。对于这(n-1)个值(从i=1开始)，内部循环迭代i/2次。因此，内部循环的总迭代次数为1+1+2+2+3+3+...+(n/2)+(n/2)=2(1+2+3+...+n/2)=2*(n/2(n/2+1))/2=n^2/4+n/2。 同样，“sum++”也执行了n^2/4+n/2次。现在考虑程序第一行的成本=c1，第二行的成本=c2，第三行的成本=c3。这些成本可能因不同的机器而异。因此，执行程序所需的总时间=c1*(n-1)+c2*(n^2/4+n/2)+c3*(n^2/4+n/2)=(c2+c3)n^2/4+(c2+c3)n/2+c1*n-c1。因此，所需的时间可以用数学函数表示。在大O符号中，你可以说它是O((c2+c3)n^2/4+(c2+c3)n/2+c1*n-c1)。在大O符号中，可以忽略低阶项和最高阶项的系数。因为对于大的n值，n^2比n大得多。因此，你可以说它是O((c1+c2)n^2/4)。此外，对于任何n值，n^2都比(c1+c2)n^2/4大一个常数因子，因此可以说它是O(n^2)。

- Tanmoy Banerjee