开会员与付费前请必须阅读这篇文章，在首页置顶第一篇：（进站必看本站VIP介绍/购买须知）
本站所有源码均为自动秒发货，默认（百度网盘）
本站所有源码均为自动秒发货，默认（百度网盘）
作为程序员，我们写的每一行代码最终都会转化为计算机的执行指令，而不同算法的执行效率天差地别——同样解决“从100万条数据中查找某个值”的问题，有的算法能瞬间出结果，有的却要卡顿几秒甚至几分钟。这背后的核心，就是算法复杂度的差异，而大O表示法，正是我们描述和对比算法效率的“通用语言”。
很多新手刚接触大O表示法时，都会被“O(n)”“O(logn)”这些符号搞懵，甚至觉得“反正能跑起来就行，分析复杂度没必要”。但实际上，当数据量达到一定规模（比如10万、100万级），复杂度的差异会直接决定程序的可用性——你写的排序算法如果是O(n²)，在10万条数据下可能要跑几分钟，而O(nlogn)的算法可能只需要几十毫秒。
今天这篇文章，就从“是什么、为什么、怎么用”三个维度，彻底讲懂大O表示法，帮你快速掌握算法复杂度分析的核心技巧，摆脱“只会写代码，不会评代码”的困境。
一、先搞懂：大O表示法到底是什么？
大O表示法（Big O Notation），本质是一种描述算法执行时间（或空间）随输入数据规模增长而变化的趋势的数学符号。它不关心算法在具体硬件、具体数据下的实际执行时间，只关心“当输入数据量n趋近于无穷大时，算法执行时间的增长量级”。
举个通俗的例子：
假设有两个算法，用来计算1到n的和：
算法A：循环n次，每次累加1，执行次数是n次；
算法B：直接用公式n*(n+1)/2，执行次数是1次。
当n=10时，算法A执行10次，算法B执行1次，差距不大；但当n=100万时，算法A执行100万次，算法B依然只执行1次——这就是“增长趋势”的差异。
大O表示法中，算法A的时间复杂度是O(n)，算法B是O(1)。这里的“O”描述的不是具体次数，而是“执行次数随n增长的变化规律”：
-
O(1)：执行次数不随n变化，是常数级，效率最高；
-
O(n)：执行次数随n线性增长，n越大，执行次数越多；
核心要点：大O表示法忽略常数项、低次项和系数。比如算法执行次数是2n+3，我们会简化为O(n)——因为当n足够大时，2倍的系数和3这个常数，对增长趋势的影响可以忽略不计；再比如n²+5n+100，会简化为O(n²)，因为n²的增长速度远快于低次项n。
二、核心本质：为什么要用大O表示法？
很多新手会疑惑：“我直接跑代码，统计一下执行时间，不就能知道算法效率了吗？” 其实这种方式有两个致命问题：
1. 实际执行时间受环境影响太大
同样一段代码，在高性能服务器上可能0.1秒跑完，在老旧电脑上可能10秒跑完；同样的电脑，数据分布不同（比如排序的数组是有序还是无序），执行时间也会有差异。而大O表示法忽略了这些外部因素，只关注算法本身的“固有效率”——无论在什么环境下，O(logn)的算法永远比O(n)的算法在大数据量下更高效。
2. 无法对比不同数据规模下的效率
当n很小时，不同复杂度的算法执行时间差距可能不大（比如n=10时，O(n²)和O(nlogn)的执行次数可能只差几十次），但当n达到10万、100万时，差距会呈指数级放大。大O表示法能帮我们提前预判算法在“大数据量场景”下的表现，这是实际测试无法做到的。
简单来说：大O表示法的核心价值，是提供了一种“跨环境、跨数据规模”的算法效率对比标准，让我们在写代码前就能判断算法的优劣，避免写出“小数据能跑，大数据卡顿”的垃圾代码。
三、常见的大O复杂度（从高效到低效排序）
开发中最常用的复杂度有以下几种，记住它们的增长趋势，就能快速判断算法效率：
1. O(1)：常数复杂度（最优）
无论输入数据n多大，算法的执行次数都是固定的，不随n变化。
典型案例：
-
访问数组的指定下标（arr[5]）；
-
简单的算术运算（比如两数相加、求绝对值）；
-
判断一个数是否为偶数。
注意：O(1)不是说只执行1次，而是执行次数固定（比如执行3次、5次），只要不随n变化，就是O(1)。
2. O(logn)：对数复杂度（次优）
执行次数随n的增长而增长，但增长速度非常慢——n越大，增长越平缓。核心是“每次操作都能将问题规模缩小一半”。
典型案例：二分查找（从有序数组中查找某个值）。
举例：从100万条有序数据中查找某个值，二分查找最多只需要20次（2²⁰≈100万），即使n扩大到10亿，也只需要30次左右——这就是O(logn)的优势。
3. O(n)：线性复杂度
执行次数和n成正比，n扩大几倍，执行次数就扩大几倍。
典型案例：
-
遍历数组（for循环从0到n-1）；
-
求数组的和、平均值；
-
线性查找（从无序数组中查找某个值）。
4. O(nlogn)：线性对数复杂度
执行次数是n乘以logn，增长速度比O(n)快，但比O(n²)慢，是主流高效排序算法的复杂度。
典型案例：快速排序、归并排序、堆排序——这些算法的核心思想是“分治”，先将问题分成logn层，每一层执行n次操作，整体就是O(nlogn)。
5. O(n²)：平方复杂度（低效）
执行次数和n的平方成正比，n扩大10倍，执行次数扩大100倍，大数据量下效率极低。
典型案例：
-
双层for循环（比如冒泡排序、插入排序的最坏情况）；
-
遍历一个n×n的二维数组。
注意：O(n²)不是不能用，而是只能用于n很小的场景（比如n<1000），一旦n超过1万，执行时间会急剧增加。
6. 其他复杂度（尽量避免）
O(2ⁿ)（指数复杂度）、O(n!)（阶乘复杂度）：增长速度极快，即使n很小（比如n=20），执行次数也会达到百万级、亿级，几乎无法用于实际开发，除非是极特殊的场景（比如小规模的回溯算法）。
四、实战技巧：如何快速计算算法的大O复杂度？
很多新手觉得“分析复杂度很难”，其实只要记住3个核心原则，就能快速算出大部分算法的复杂度，无需复杂的数学推导。
原则1：只关注“最耗时的部分”
算法的整体复杂度，由执行次数最多的部分决定。比如一段代码中，有一个O(n)的循环，还有一个O(1)的操作，整体复杂度就是O(n)——因为O(n)的部分是最耗时的，O(1)的部分可以忽略。
示例代码：
// 计算1到n的和 public int sum(int n) { int result = 0; // O(1) for (int i = 1; i <= n; i++) { // O(n)，最耗时 result += i; } return result; // O(1) } // 整体复杂度：O(n)
原则2：嵌套代码取“乘积”，并列代码取“最大值”
1. 嵌套代码（比如双层for循环）：复杂度是各层复杂度的乘积。
示例（冒泡排序核心代码）：
for (int i = 0; i < n; i++) { // 外层O(n) for (int j = 0; j < n – i – 1; j++) { // 内层O(n) if (arr[j] > arr[j+1]) { // 交换操作，O(1) int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } // 整体复杂度：O(n) * O(n) = O(n²)
2. 并列代码（多个独立的循环）：复杂度是各部分复杂度的最大值。
// 并列两个循环 for (int i = 0; i < n; i++) { // O(n) System.out.println(i); } for (int i = 0; i < n; i++) { // O(n) for (int j = 0; j < n; j++) { // O(n) System.out.println(i + j); } } // 整体复杂度：max(O(n), O(n²)) = O(n²)
原则3：忽略常数项、低次项和系数
这是大O表示法的核心规则，也是最容易被新手忽略的点。
-
执行次数=2n+3 → 简化为O(n)（忽略系数2和常数3）；
-
执行次数=n²+5n+100 → 简化为O(n²)（忽略低次项5n和常数100）；
-
执行次数=3logn+2 → 简化为O(logn)（忽略系数3和常数2）。
为什么可以忽略？因为当n趋近于无穷大时，这些项对增长趋势的影响微乎其微。比如n=100万时，2n=200万，3n=300万，差距只有50%；但n²=1e12，5n=500万，5n对n²的影响几乎可以忽略。
五、常见误区：这些错误千万别犯！
误区1：把O(n)和“执行n次”划等号
大O表示法描述的是“增长趋势”，不是具体执行次数。比如一段代码执行次数是3n，它的复杂度依然是O(n)，而不是O(3n)——因为系数不影响增长趋势。
误区2：认为O(logn)比O(1)高效
O(1)是常数级，无论n多大，执行次数都固定；而O(logn)虽然增长慢，但n越大，执行次数越多。比如n=100时，O(logn)可能执行7次，O(1)执行1次，显然O(1)更高效。只有当n足够大时，O(logn)才会比O(n)高效，但永远不如O(1)。
误区3：忽略“最坏情况”和“平均情况”
很多算法的复杂度会随数据分布变化，我们通常分析的是“最坏情况”（保证算法的最坏表现），有时也会分析“平均情况”。
比如快速排序：最坏情况下复杂度是O(n²)（当数组已经有序时），但平均情况下是O(nlogn)——我们平时说快速排序的复杂度是O(nlogn)，指的是平均情况。
六、总结：大O表示法的核心价值
大O表示法不是一门高深的数学知识，而是程序员必备的“算法效率判断工具”。它的核心是“忽略细节，关注趋势”，让我们在写代码时就能预判算法在大数据量下的表现，避免写出低效代码。
记住以下几点，就能轻松掌握大O表示法：
-
大O描述的是“执行时间随n增长的趋势”，不是具体执行时间；
-
忽略常数项、低次项和系数，只保留最高次项；
-
嵌套取乘积，并列取最大值；
-
常用复杂度优先级：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)。
最后，算法复杂度分析不是“纸上谈兵”，而是要结合实际开发场景——比如如果你的数据量很小（n<1000），即使是O(n²)的算法也能正常运行；但如果数据量达到10万级以上，就必须选择O(nlogn)及以上效率的算法。
希望这篇文章能帮你彻底搞懂大O表示法，下次写算法时，不再只关注“能不能跑”，更能关注“能不能跑得更快”～
