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

Question

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

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

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

显然(我不得不同意)，这个“双循环”是O(n²):

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

这是我感到困惑的地方:

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

第二个“双循环”的复杂度也为 O(n²)，但显然(在最坏的情况下)比第一个好(？)很多。

我错过了什么？信息是否准确？谁能解释一下这个“现象”？

Answer 1

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

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

有时创建图表并查看出现的线条类型会有所帮助:

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