O(N^2) 复杂度意味着什么

在分析算法时，考虑算法如何随着输入规模的增加而运行至关重要。大 O 表示法是计算机科学家用来对算法进行分类的关键统计量，它表示算法执行时间的增长顺序。O(N^2) 算法是一类重要且流行的 Big O，其执行时间随着输入量的增加呈二次方增长。对于大规模输入，具有这种时间复杂度的算法被认为效率低下，因为将输入大小加倍会导致运行时间增加四倍。

本文将探讨 Big O(N^2) 的含义，分析一些二次方算法的示例，并讨论为什么这种复杂度可能对大型数据集造成问题。理解 O(N^2) 等算法复杂度类别，可以让我们根据不同的用例来表征不同算法的可伸缩性和效率。

不同的 Big Oh 表示法。

O(1) - 常数时间

O(1) 算法的完成时间与输入大小无关。一个很好的例子是使用索引检索数组元素。在哈希表或字典中查找键通常也是 O(1)。这些操作非常快，即使对于大型输入也是如此。

O(log N) - 对数时间

具有对数时间复杂度的算法非常高效。对于排序数组，二分查找是 O(log N) 的经典示例，因为每次迭代搜索空间都会减半。在平衡搜索树中查找项目也需要 O(log N) 时间。对数运行时间随 N 缓慢增长。

O(N) - 线性时间

线性复杂度算法至少遍历输入一次。排序、搜索未排序数据或访问数组中每个元素的简单算法需要 O(N) 时间。随着数据集变大，线性运行时间可能会变得太慢。但线性仍然远优于二次方或指数运行时间。

O(N log N) - 对数线性时间

这种复杂度会导致像 归并排序 和 堆排序 这样的低效排序算法。这些算法将数据分成小块，对每个块进行排序 (O(N))，然后合并结果 (O(log N))。旨在提高效率的良好设计的算法通常具有对数线性运行时间。

O(N^2) - 二次方时间

二次方算法涉及对数据的嵌套迭代。冒泡排序和插入排序等简单排序方法是 O(N^2)。矩阵运算（如乘法）也通常是 O(N^2)。对于大规模输入，二次方增长变得不可行。对于大数据，需要更复杂的算法。

O(2^N) - 指数时间

指数运行时间在算法中不好。仅将一个元素添加到输入中就会使处理时间加倍。斐波那契数列的递归计算是经典的指数时间示例。指数增长使得这些算法对于即使是中等规模的输入也是不切实际的。

什么是 Big O(N^2)?

• O(N^2) 算法的运行时间与输入大小 N 的平方成正比增长。
• 将输入大小加倍会使运行时间增加四倍。如果对 10 个元素运行需要 1 秒，那么对 20 个元素大约需要 4 秒，对 40 个元素需要 16 秒，依此类推。
• O(N^2) 算法涉及对数据的嵌套迭代。例如，检查每对可能的元素或在二维矩阵上进行操作。
• 冒泡排序、插入排序和选择排序等简单排序算法通常是 O(N^2)。比较和交换相邻元素会导致嵌套循环。
• 暴力搜索算法通常是 O(N^2)。检查每个子数组或子字符串是否满足条件需要嵌套循环。
• 像 NxN 矩阵乘法这样的基本矩阵运算是 O(N^2)。乘积矩阵的每个元素都取决于输入矩阵的行和列。
• 图算法，如用于查找所有顶点对之间最短路径的 Floyd-Warshall 算法，其复杂度为 O(N^2)。会检查顶点之间的每条可能路径。
• O(N^2) 对于小输入来说是可以接受的，但对于大型数据集来说会非常慢。具有二次方复杂度的算法无法很好地扩展。
• 对于大型输入，应优先选择更高效的算法，例如归并排序 O(N log N) 和矩阵乘法 O(N^2.807)，而不是 O(N^2) 算法。
• 然而，对于输入不无限增长的小型本地数据集，O(N^2) 可能仍然是合理的。

二次方时间复杂度的不同属性？

• 运行时间与输入大小 N 的平方成正比增长。将 N 加倍会使运行时间 **翻四倍**。
• 涉及对数据集的嵌套迭代或操作。例如，处理二维数组的嵌套 for 循环。
• 具有嵌套循环遍历数据的算法很可能是 O(N^2)。
• 冒泡排序、插入排序和选择排序等排序算法是具有 O(N^2) 运行时间的常见示例。
• 每个元素与所有其他元素进行暴力比较是 O(N^2)。例如，检查数组中的所有可能对。
• NxN 矩阵上的基本运算，如乘法或求行列式，通常是 O(N^2)。
• 图算法，如用于查找最短路径的 Floyd-Warshall 算法，它会探索每个顶点对之间的关系，其复杂度为 O(N^2)。
• 运行时间可以更正式地表示为 cN^2 + bN + a，其中 c、b 和 a 是常数。但为了简单起见，我们省略了常数。
• 二次方算法对于大规模输入会变得极其缓慢。将 N 加倍会使算法慢 4 倍。
• O(N^2) 对于现实世界的大数据应用通常效率太低。因此，人们倾向于使用更快的算法。
• 但是，对于 N 有限的小型数据集，快速的 O(N^2) 实现可能很有用。
• 在分析算法的整体性能时，但选择算法时，常数和实际因素也很重要。

具有二次方时间复杂度的流行算法

冒泡排序： 在对列表进行冒泡排序时，会比较相邻的元素，如果顺序错误则交换它们。需要嵌套循环，导致 O(N^2)。

插入排序： 其工作方式与冒泡排序类似，但将元素插入到已排序的位置。内部循环会移动元素，也为 O(N^2)。

选择排序： 它找到未排序的最小元素并将其交换到前面。内部循环搜索剩余的未排序区域，因此为 O(N^2)。

矩阵乘法： 每个元素都取决于用于相乘的行和列，以相乘两个 N x N 矩阵。嵌套循环导致 O(N^2)。

Floyd-Warshall 算法： 查找图中所有顶点对之间的最短路径。遍历所有顶点组合的复杂度为 O(N^2)。

暴力字符串搜索： 在长度为 N 的字符串中检查大小为 M 的所有子字符串的复杂度为 O(N^2)。

检查所有对： 在数组中查找满足某些条件的对需要嵌套循环来检查所有组合 - O(N^2)。

图像处理滤波器：模糊等操作为 O(N^2)，它处理像素邻域，其中包含图像上的嵌套循环。

示例

让我们来看一个 **二次方时间复杂度** 的 C 语言程序。

输出

Enter a positive integer: 5
Sum of first 5 natural numbers is 35

说明

• 此程序使用嵌套的 for 循环计算前 N 个自然数的总和。
• 外层循环迭代 N 次，以处理从 1 到 N 的每个数字。
• 为了累加每个数字，内层循环从 1 迭代到当前数字 i。
• 因此，对于输入 5，它计算
  1
  1+2
  1+2+3
  1+2+3+4
  1+2+3+4+5
• 内层循环执行 1 + 2 + 3 + ... + N 次，这是 O(N^2) 的工作量。
• 运行时间随着 N 的平方而增长。因此，这演示了一个具有二次方时间复杂度的算法。

结论

总而言之，Big O(N^2) 是一个重要的算法时间复杂度类别，需要理解。它指的是随着输入规模的增加，运行时间呈二次方增长的算法。在许多常见算法中都可以看到产生 O(N^2) 增长率的嵌套迭代或数据操作，包括基本的排序方法、矩阵乘法、Floyd-Warshall 以及其他图算法。虽然简单的 O(N^2) 算法对于小问题规模可能很有用，但对于更大的输入，它们的性能会迅速下降，输入规模翻倍会导致运行时间翻四倍。对于大型数据集和实时应用程序，应尽可能使用具有更好渐近复杂度的算法，例如 O(N log N)。了解常见的算法复杂度并为问题规模和性能需求选择合适的算法，是设计高效程序和应用程序的关键技能。