这两个嵌套循环真的具有相同的二次时间复杂度吗？

Question

这是我想出的算法的一部分：

\n\n

for (int i = 0; i < n - 1; i++)\n   for (int j = i; j < n; j++)\n      (...)\n

\n\n

我正在使用这个“双循环”来测试大小为 n 的数组中所有可能的 2 元素和。

\n\n

显然（我必须同意它），这个“双循环”是O(n\xc2\xb2)：

\n\n

n + (n-1) + (n-2) + ... + 1 = sum from 1 to n = (n (n - 1))/2\n

\n\n

这是我感到困惑的地方：

\n\n

for (int i = 0; i < n; i++)\n   for (int j = 0; j < n; j++)\n      (...)\n

\n\n

当第二个“双循环”O(n\xc2\xb2)明显（在最坏的情况下）比第一个“双循环”好得多（？）时，其复杂度也为 。

\n\n

我缺少什么？信息准确吗？有人能解释一下这个“现象”吗？

\n

Answer 1

(n (n - 1))/2简化为n\xc2\xb2/2 - n/2. 如果您使用非常大的数字n， 的增长率与n/2相比将相形见绌n\xc2\xb2，因此为了计算 Big-O 复杂性，您实际上忽略了它。同样，“常数”值 1/2 根本不会随着增加而n增加，因此您也可以忽略它。那只会给你留下n\xc2\xb2.

\n\n

请记住，复杂性计算与“速度”不同。一种算法可能比另一种算法慢五千倍，但 Big-O 复杂度仍然较小。但当你增加到n非常大的数字时，就会出现一般模式，通常可以使用简单的公式进行分类：1、log n、n、n log n、n\xc2\xb2等。

\n\n

有时创建一个图表并查看出现什么样的线条会有所帮助：

\n\n

\n

\n\n

尽管这两个图的缩放系数非常不同，但您可以看到它生成的曲线类型几乎完全相同。

\n