Big-O 表示法简介（基础入门)

我们在学习计算机科学时会学到算法中的大O符号。

事实上，我们大多数人只是简单地理解为：

越接近O(1)，复杂度越低，计算越快，越好；越接近O(n!)，复杂度越高，计算越慢，越不好。

那么，大O的定义是什么？它又是怎么产生的呢？让我们来探讨一下。

大O符号的起源

大O符号最早由德国数学家**保罗·巴赫曼（Paul Bachmann）**于1894年在他的著作《解析数论》中首次提出。巴赫曼引入这个符号是为了比较和近似表达函数的增长率。后来，**埃德蒙·兰道（Edmund Landau）**进一步完善并推广了这一概念。兰道将其称为“兰道符号（Landau notation）”，并在计算机科学中作为计算算法复杂度的强大工具被广泛使用。

此外，大O符号还有其他变体，比如表示下界的“大Ω”符号，以及同时表示上下界的“大Θ”符号。

（华盛顿大学CSE 373讲义）

当有两个函数f(n)和g(n)时，f(n)=O(g(n))意味着对于足够大的n，存在一个正常数C，使得：

∣f(n)∣≤C⋅∣g(n)∣

也就是说，f(n)可以用g(n)的常数倍来作为上界（upper bound）。

举个例子：

如果f(n)=3n²+2n+1，则f(n)是O(n²)。

因为只考虑最高次项n²，并忽略常数系数。

那么，如果f(n)=2n +10呢？

聪明的人可能已经猜到了，f(n) = O(n)。

总之，大O符号是用来表示函数的渐进增长率（asymptotic growth rate）的。

如果觉得这有点难理解，简单来说就是：

随着输入规模增大，函数复杂度的增长情况。

(img ref:EP132: Big O Notation 101: The Secret to Writing Efficient Algorithms )

Big-O的概念就是这样，通常我们会用Big-O来计算两种复杂度：

时间复杂度（Time Complexity）

• 表示随着输入规模增大，算法执行所需时间（操作次数）的增长率。

常见的时间复杂度

• O(1)→ 常数时间（Constant Time）

  • 示例：通过索引访问数组元素（如arr[2]），或在哈希表中查找键值（无冲突的情况下）。
  • 解释：与输入规模(n)无关，操作一步完成。

• O(log n)→ 对数时间（Logarithmic Time）

  • 示例：二分查找、平衡二叉搜索树（BST）中查找节点。
  • 解释：每次操作将输入规模减半（例如不断分割数据进行查找）。

• O(n)→ 线性时间（Linear Time）

  • 示例：遍历数组的所有元素，链表中查找特定值。
  • 解释：操作时间随输入规模(n)线性增长。

• O(n log n)→ 线性对数时间（Linearithmic Time）

  • 示例：归并排序（Merge Sort）、快速排序（Quick Sort）、堆排序（Heap Sort）。
  • 解释：采用分治策略（Divide and Conquer），将n个元素反复分成两半(log n)，然后合并(n)。

• O(n²)→ 平方时间（Quadratic Time）

  • 示例：嵌套循环检查数组的所有组合（如冒泡排序、选择排序），图中所有节点对的最短路径计算（Floyd-Warshall算法）。
  • 解释：输入规模增大时，操作时间呈平方级爆炸式增长。

• O(2ⁿ)→ 指数时间（Exponential Time）

  • 示例：斐波那契数列的朴素递归实现（重复计算多），生成所有子集（Subset）。
  • 解释：即使输入规模较小，操作时间也呈指数级增长，不实用。

空间复杂度（Space Complexity）

• 表示随着输入规模增大，算法使用的内存增长情况。

常见的空间复杂度

• O(1)→ 常数空间（Constant Space）

  • 示例：单个变量使用（如循环中的索引i），与输入规模无关的固定大小变量（如int a = 10）。
  • 解释：与输入规模(n)无关，使用固定内存。

• O(log n)→ 对数空间（Logarithmic Space）

  • 示例：平衡二叉搜索树（BST）的递归遍历（递归调用栈深度），快速排序的平均空间复杂度（分治时栈深度）。
  • 解释：递归或分治算法中，栈/内存使用量与输入规模的对数成正比。

• O(n)→ 线性空间（Linear Space）

  • 示例：存储输入数组的副本（如newArr = arr.slice()），图的邻接表表示（与节点数成正比的内存）。
  • 解释：内存使用量随输入规模(n)线性增长。

• O(n²)→ 平方空间（Quadratic Space）

  • 示例：图的邻接矩阵表示（n x n矩阵），动态规划（DP）的二维表（如最长公共子序列）。
  • 解释：内存使用量随输入规模的平方增长，处理大规模数据时效率低下。

• O(2ⁿ)→ 指数空间（Exponential Space）

  • 示例：存储所有子集（Subset），递归斐波那契的最差空间复杂度（重复调用栈）。
  • 解释：即使输入规模较小，内存使用量也呈指数级增长。

两者都用大O符号表示，并假设最坏情况（Worst Case）来分类性能。

区别在于：

• 时间复杂度关注速度，而空间复杂度关注内存使用。

权衡（Trade-off）

• 快速算法可能消耗更多内存（如动态规划），
• 或者节省内存但增加时间消耗（如递归与迭代对比）。

例如，使用更多内存来降低时间复杂度的一个例子是哈希表。

时间复杂度表 (Time Complexity Table)

1. 插入排序 (Insertion Sort)

最佳情况 (Best):
O(n)
当数据已经排序时，每个元素只需比较而无需移动位置。
例如: [1, 2, 3, 4] 只需比较，无需插入。

平均情况 (Average):
O(n²)
当数据随机分布时，每个元素平均需要移动一半的位置。

最坏情况 (Worst):
O(n²)
当数据完全逆序时，每个元素需要与所有前面的元素进行比较和移动。
例如: [4, 3, 2, 1] 中，每个元素最多需要 n 次比较和移动。

2. 选择排序 (Selection Sort)

最佳、平均、最坏情况:
均为 O(n²)
原因：无论输入数据的状态如何，每一步都需要在剩余数组中找到最小值（或最大值），因此比较次数始终固定。
即使在最佳情况下，交换次数减少，但比较次数不变。

3. 冒泡排序 (Bubble Sort)

最佳情况 (Best):
O(n)
当数据已经排序时，一次扫描后如果没有发生交换即可提前结束。
例如: [1, 2, 3, 4] 不会发生交换，因此只需一次完整扫描后结束。

平均情况 (Average):
O(n²)
在随机数据中，每个元素平均需要移动到一半的位置。

最坏情况 (Worst):
O(n²)
当数据完全逆序时，每个元素最多需要 n 次比较和交换。
例如: [4, 3, 2, 1] 中，每个元素需要逐个移动。

4. 归并排序 (Merge Sort)

最佳、平均、最坏情况:
均为 O(n log n)
原因：归并排序通过分治法（Divide and Conquer）将数据分为两部分，并在合并过程中始终保持相同的工作量。
无论输入数据的状态如何，分治和合并过程都以相同的方式进行。

5. 快速排序 (Quick Sort)

最佳情况 (Best):
O(n log n)
当每次选择的基准值（Pivot）都能将数据均匀划分时，达到平衡划分。
例如: [4, 1, 3, 2, 6, 5] 中，基准值为中间值时。

平均情况 (Average):
O(n log n)
大多数情况下，基准值能选择在较为平衡的位置，从而保持 O(n log n) 的性能。

最坏情况 (Worst):
O(n²)
当基准值总是选择为最小值或最大值时，导致不平衡划分。
例如: [1, 2, 3, 4, 5] 已经排序的数据中，若选择第一个元素为基准值，则每次只划分一侧。

6. 堆排序 (Heap Sort)

最佳、平均、最坏情况:
均为 O(n log n)
原因：堆排序利用堆数据结构提取数据时，始终保持相同的工作量。
无论输入数据的状态如何，堆的构建和提取过程都以相同方式进行。

7. 希尔排序 (Shell Sort)

最佳情况 (Best):
O(n log n)
当间隔（Gap）设置合理且数据接近排序状态时效率较高。

平均情况 (Average):
O(n^1.3)
一般情况下，随着间隔逐渐减小，数据逐步排序。

最坏情况 (Worst):
O(n²)
当间隔设置不合理或数据完全逆序时效率较低。

8. 计数排序 (Counting Sort)

最佳、平均、最坏情况:
均为 O(n + k)
原因：当数据范围（k）较小时，直接通过计算对数据进行排序，因此无论输入数据状态如何，性能相同。
但当 k 较大时，内存使用量会增加。

9. 基数排序 (Radix Sort)

最佳、平均、最坏情况:
均为 O(nk)
原因：按位排序时，工作量与数据大小（n）和位数（k）成正比。
无论输入数据状态如何，性能相同。

10. 桶排序 (Bucket Sort)

最佳情况 (Best):
O(n)
当数据均匀分布且桶内无需排序时。

平均情况 (Average):
O(n + k)
当数据大致均匀分布，但桶内需要少量排序时。

最坏情况 (Worst):
O(n²)
当数据集中在一个桶中时，该桶内的排序成本显著增加。

空间复杂度表 (Space Complexity Table)

1. 插入排序、选择排序、冒泡排序、堆排序、希尔排序

这些都是原地(In-place)排序算法，几乎不需要额外的内存。
空间复杂度始终为O(1)。

2. 归并排序

需要额外的数组来存储分治后的子数组。
空间复杂度始终为O(n)，这是归并排序的主要缺点之一。

3. 快速排序

由于递归调用栈的存在，需要额外的内存。
平均情况下需要O(logn)的空间，而在最坏情况下可能增加到O(n)。

4. 计数排序

根据数据范围（k）需要额外的内存。
空间复杂度为O(k)。

5. 基数排序

按照每个位数进行排序，因此需要与数据大小（n）和范围（k）成比例的额外内存。
空间复杂度为O(n+k)。

6. 桶排序

将数据分配到桶中存储，因此需要与数据大小和桶的数量成比例的额外内存。
空间复杂度为O(n+k)。

But, 这篇文章并不是为了从数学角度整理排序算法的Big-O，而是为了说明Big-O的局限性。

所有模型都是错的，但有些是有用的。
——乔治·爱德华·佩尔汉姆·博克斯（George Edward Pelham Box），数学家

Big-O 是一种简化的复杂度模型，无法包含现实中的所有变量。
它只是用来快速比较算法效率的一种方式。

那么，让我们来看一个例子。

Big-O的局限性

1. Big-O基于最坏情况（Worst Case）

using System; using System.Diagnostics; class QuickSortExample { // 最坏情况（已排序数组） static int[] QuickSortWorst(int[] arr) { if (arr.Length <= 1) return arr; int pivot = arr[0]; // 选择第一个元素作为基准点（引发最坏情况） var left = Array.FindAll(arr, x => x <= pivot); var right = Array.FindAll(arr, x => x > pivot); return Concatenate(QuickSortWorst(left), pivot, QuickSortWorst(right)); } // 平均情况（随机基准点） static int[] QuickSortAvg(int[] arr) { if (arr.Length <= 1) return arr; int pivot = arr[arr.Length / 2]; // 选择中间元素作为基准点 var left = Array.FindAll(arr, x => x < pivot); var middle = Array.FindAll(arr, x => x == pivot); var right = Array.FindAll(arr, x => x > pivot); return Concatenate(QuickSortAvg(left), middle, QuickSortAvg(right)); } // 数组连接辅助函数 static int[] Concatenate(int[] left, int pivot, int[] right) { var result = new int[left.Length + 1 + right.Length]; Array.Copy(left, result, left.Length); result[left.Length] = pivot; Array.Copy(right, 0, result, left.Length + 1, right.Length); return result; } static void Main() { int[] arrSorted = new int[1000]; // 已排序数组（最坏情况） for (int i = 0; i < arrSorted.Length; i++) arrSorted[i] = i; int[] arrRandom = new int[1000]; // 随机数组 Random rand = new Random(); for (int i = 0; i < arrRandom.Length; i++) arrRandom[i] = rand.Next(1000); // 测量最坏情况的时间 var stopwatch = Stopwatch.StartNew(); QuickSortWorst(arrSorted); Console.WriteLine($"最坏情况: {stopwatch.Elapsed.TotalMilliseconds}ms"); // 测量平均情况的时间 stopwatch.Restart(); QuickSortAvg(arrRandom); Console.WriteLine($"平均情况: {stopwatch.Elapsed.TotalMilliseconds}ms"); } }

例如，快速排序在平均情况下是O(n log n)，但在最坏情况下是O(n²)。根据Big-O的定义，它会被标记为O(n²)。然而，在实际编程中，快速排序的表现往往优于理论上的最坏情况。

此外，O(n²)的算法在某些情况下可能比O(n log n)更快，尤其是在小规模数据中，由于缓存局部性（cache locality）的原因。

2. 忽略常数因子（Constant Factor）

using System; using System.Diagnostics; class ConstantCoefficientExample { static int F(int n) { return 100 * n + 1000; // O(n) } static int G(int n) { return (int)(0.1 * n * n); // O(n²) } static void Main() { int n = 10; // 小输入规模 var stopwatch = Stopwatch.StartNew(); F(n); Console.WriteLine($"O(n) 函数执行时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); stopwatch.Restart(); G(n); Console.WriteLine($"O(n²) 函数执行时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); } }

例如，如果有两个函数f(n)=100n+1000和g(n)=0.1n²，Big-O会将它们分别归类为O(n)和O(n²)。但在小规模n的情况下，g(n)可能会更快。

3. 相同复杂度也可能有性能差异

快速排例代码 (QuickSort Example)

using System; using System.Diagnostics; class QuickSortExample { static void QuickSort(int[] arr, int left, int right) { if (left < right) { int pivotIndex = Partition(arr, left, right); QuickSort(arr, left, pivotIndex - 1); // 对左子数组进行排序 QuickSort(arr, pivotIndex + 1, right); // 对右子数组进行排序 } } static int Partition(int[] arr, int left, int right) { int pivot = arr[right]; // 选择基准点（这里选择最后一个元素） int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] < pivot) { i++; Swap(arr, i, j); } } Swap(arr, i + 1, right); // 将基准点移动到正确位置 return i + 1; } static void Swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void Main() { int[] arr = { 3, 6, 8, 10, 1, 2, 1 }; Console.WriteLine("排序前: " + string.Join(", ", arr)); var stopwatch = Stopwatch.StartNew(); QuickSort(arr, 0, arr.Length - 1); Console.WriteLine($"快速排序时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); Console.WriteLine("排序后: " + string.Join(", ", arr)); } }

堆排序示例代码 (HeapSort Example)

using System; using System.Diagnostics; class HeapSortExample { static void HeapSort(int[] arr) { int n = arr.Length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i); // 从堆中逐个提取元素 for (int i = n - 1; i > 0; i--) { Swap(arr, 0, i); // 将根节点（最大值）与最后一个元素交换 Heapify(arr, i, 0); // 缩小堆大小并重新构建堆 } } static void Heapify(int[] arr, int n, int i) { int largest = i; // 父节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 如果左子节点更大 if (left < n && arr[left] > arr[largest]) largest = left; // 如果右子节点更大 if (right < n && arr[right] > arr[largest]) largest = right; // 如果最大值不是父节点 if (largest != i) { Swap(arr, i, largest); Heapify(arr, n, largest); // 递归地调整子树 } } static void Swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void Main() { int[] arr = { 3, 6, 8, 10, 1, 2, 1 }; Console.WriteLine("排序前: " + string.Join(", ", arr)); var stopwatch = Stopwatch.StartNew(); HeapSort(arr); Console.WriteLine($"堆排序时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); Console.WriteLine("排序后: " + string.Join(", ", arr)); } }

排序比较代码 (SortComparison)

using System; using System.Diagnostics; class SortComparison { static void Main() { int[] arr = new int[100000]; Random rand = new Random(); for (int i = 0; i < arr.Length; i++) arr[i] = rand.Next(100000); // 测量快速排序的时间 var stopwatch = Stopwatch.StartNew(); QuickSort((int[])arr.Clone(), 0, arr.Length - 1); Console.WriteLine($"快速排序时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); // 测量堆排序的时间 stopwatch.Restart(); HeapSort((int[])arr.Clone()); Console.WriteLine($"堆排序时间: {stopwatch.Elapsed.TotalMilliseconds}ms"); } static void QuickSort(int[] arr, int left, int right) { if (left < right) { int pivotIndex = Partition(arr, left, right); QuickSort(arr, left, pivotIndex - 1); QuickSort(arr, pivotIndex + 1, right); } } static int Partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] < pivot) { i++; Swap(arr, i, j); } } Swap(arr, i + 1, right); return i + 1; } static void HeapSort(int[] arr) { int n = arr.Length; for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { Swap(arr, 0, i); Heapify(arr, i, 0); } } static void Heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { Swap(arr, i, largest); Heapify(arr, n, largest); } } static void Swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

例如，快速排序和堆排序的理论复杂度相同，但由于堆排序的常数因子较大且缓存效率较低，因此在实际应用中通常比快速排序慢。

此外，输入数据的特性、错误数据、输入规模等因素都会导致实际表现与Big-O不符。

硬件环境和缓存局部性等问题也会导致性能差异。

正如我之前的文章提到的，即使是相同的复杂度，仅仅是因为双重循环是以行优先还是列优先的方式进行，缓存未命中率的不同也会导致速度差异。

结论

Big-O是一个非常强大的工具，但它并不是万能的。我们不能盲目崇拜理论，认为它可以解决一切问题。现实世界的问题总是复杂多样的，理论只是现实的一部分抽象。

因此，我们应该将理论作为解决问题的指南针，但也要注意观察周围的“风景”，确保我们走在正确的道路上。