这两个嵌套循环真的具有相同的二次时间复杂度吗？ [英] Do these two nested loops really have the same quadratic time complexity?

问题描述

以下是我想出的一个算法的一段：

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

我正在使用这个"双循环"来测试大小为n的an数组中所有可能的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²)的复杂性，而它显然(在最坏的情况下)太多(？)比第一个好。

我错过了什么？这些信息准确吗？有人能解释一下这个"现象"吗？

推荐答案

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

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

创建图表并查看出现哪种类型的线有时很有帮助：

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

这篇关于这两个嵌套循环真的具有相同的二次时间复杂度吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！