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²2n1则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)排序算法最佳情况 (Best)平均情况 (Average)最差情况 (Worst)插入排序 (Insertion Sort)O(n)O(n²)O(n²)选择排序 (Selection Sort)O(n²)O(n²)O(n²)冒泡排序 (Bubble Sort)O(n)O(n²)O(n²)归并排序 (Merge Sort)O(nlogn)O(nlogn)O(nlogn)快速排序 (Quick Sort)O(nlogn)O(nlogn)O(n²)堆排序 (Heap Sort)O(nlogn)O(nlogn)O(nlogn)希尔排序 (Shell Sort)O(nlogn)O(n^1.3)O(n²)计数排序 (Counting Sort)O(nk)O(nk)O(nk)基数排序 (Radix Sort)O(nk)O(nk)O(nk)桶排序 (Bucket Sort)O(nk)O(nk)O(n²)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)排序算法最佳情况 (Best)平均情况 (Average)最差情况 (Worst)插入排序 (Insertion Sort)O(1)O(1)O(1)选择排序 (Selection Sort)O(1)O(1)O(1)冒泡排序 (Bubble Sort)O(1)O(1)O(1)归并排序 (Merge Sort)O(n)O(n)O(n)快速排序 (Quick Sort)O(logn)O(logn)O(n)堆排序 (Heap Sort)O(1)O(1)O(1)希尔排序 (Shell Sort)O(1)O(1)O(1)计数排序 (Counting Sort)O(k)O(k)O(k)基数排序 (Radix Sort)O(nk)O(nk)O(nk)桶排序 (Bucket Sort)O(nk)O(nk)O(n²)1. 插入排序、选择排序、冒泡排序、堆排序、希尔排序这些都是原地(In-place)排序算法几乎不需要额外的内存。空间复杂度始终为O(1)。2. 归并排序需要额外的数组来存储分治后的子数组。空间复杂度始终为O(n)这是归并排序的主要缺点之一。3. 快速排序由于递归调用栈的存在需要额外的内存。平均情况下需要O(logn)的空间而在最坏情况下可能增加到O(n)。4. 计数排序根据数据范围k需要额外的内存。空间复杂度为O(k)。5. 基数排序按照每个位数进行排序因此需要与数据大小n和范围k成比例的额外内存。空间复杂度为O(nk)。6. 桶排序将数据分配到桶中存储因此需要与数据大小和桶的数量成比例的额外内存。空间复杂度为O(nk)。But, 这篇文章并不是为了从数学角度整理排序算法的Big-O而是为了说明Big-O的局限性。所有模型都是错的但有些是有用的。——乔治·爱德华·佩尔汉姆·博克斯George Edward Pelham Box数学家Big-O 是一种简化的复杂度模型无法包含现实中的所有变量。它只是用来快速比较算法效率的一种方式。那么让我们来看一个例子。Big-O的局限性1. Big-O基于最坏情况Worst Caseusing 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 Factorusing 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)100n1000和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是一个非常强大的工具但它并不是万能的。我们不能盲目崇拜理论认为它可以解决一切问题。现实世界的问题总是复杂多样的理论只是现实的一部分抽象。因此我们应该将理论作为解决问题的指南针但也要注意观察周围的“风景”确保我们走在正确的道路上。