详解如何快速搞定常用时间复杂度

对于每一个编程入门者来说，时间复杂度都是一道绕不开的坎。写了一段代码，怎么判断它运行得快不快?不同写法的代码，效率差距到底有多大?面对算法题，怎么说明你的解法是最优的?答案都藏在时间复杂度分析里。其实时间复杂度并不难，它不需要复杂的数学推导，只要掌握几个常用规则和典型场景，就能快速搞定绝大多数日常开发和面试中的分析需求。本文就带你用最简单的方式，快速掌握常用的时间复杂度分析方法。

一、为什么需要时间复杂度?跳出“跑一遍看快慢”的误区

很多初学者刚接触编程的时候，会觉得判断代码快慢很简单：直接跑一遍，记一下运行时间不就行了?但这种方法其实有非常大的局限：

首先，运行时间高度依赖运行环境——你的代码在最新的M系列芯片上跑和在十年前的老旧单片机上跑，速度可能差几百倍，同一个代码在不同机器上得到的运行时间完全没有可比性;其次，运行时间还和输入数据的大小有关——给10个元素排序和给100万个元素排序，耗时天差地别，我们需要一种不依赖具体输入就能描述代码效率增长趋势的方法;最后，当我们对比两个不同算法的时候，小规模数据下可能看不出差距，当数据量增大之后，不同时间复杂度的算法差距会呈指数级拉开。

时间复杂度就是为了解决这个问题而生的，它是一种描述算法运行时间随输入规模增长趋势的方法，不依赖具体硬件和环境，也能清晰体现算法的效率优劣。它的核心思想是“抓大放小”：忽略常数系数和低阶项，只保留最高阶的增长项，用最简单的形式体现增长趋势，这种表示方法也叫做“大O表示法”，是我们最常用的时间复杂度表示方式。

举个简单的例子：如果一个算法的运行时间是3n² + 2n + 5，其中n是输入数据规模，用大O表示法就会简化成O(n²)，因为当n非常大的时候，低阶的2n和常数5对增长趋势的影响可以忽略不计，系数3也不改变增长的速度，所以只需要保留最高阶的n²就足够了。

二、大O表示法的核心规则：三个简单原则快速推导

其实推导时间复杂度只需要记住三个简单的规则，就能搞定90%以上的场景：

规则一：循环执行次数决定复杂度，只看最高阶

对于顺序执行的代码，复杂度只由执行次数最多的那段代码决定，低阶代码可以直接忽略。比如我们计算1到n的和：

int sum = 0; // 执行1次

for (int i = 1; i <= n; i++) { // 循环执行n次

sum += i; // 循环体执行1次，总执行n次

}

总的执行次数是n + 1，最高阶是n，所以时间复杂度就是O(n)，常数项1可以直接忽略。

如果是两层嵌套循环呢?比如我们常见的冒泡排序内层逻辑：

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

// 操作执行一次

}

}

外层循环执行n次，内层每一轮也执行n次，总执行次数是n * n = n²，所以时间复杂度就是O(n²)，嵌套循环的复杂度就是各层循环次数相乘。

规则二：分支取最大，对数看折半

如果代码里有条件分支，那时间复杂度取分支中复杂度最高的那个，因为我们分析的是最坏情况下的增长趋势。比如你在数组里找一个数，找到了直接返回，找不到继续遍历，最坏情况下要遍历整个数组，所以复杂度还是O(n)。

那什么时候会出现对数复杂度?最常见的场景就是每次循环都把问题规模折半，典型例子就是二分查找：

int left = 0, right = n - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (arr[mid] == target) return mid;

else if (arr[mid] < target) left = mid + 1;

else right = mid - 1;

}

每次循环我们都会把查找范围缩小一半，从n到n/2再到n/4……直到范围缩小到1，那一共需要循环多少次呢?我们可以算一下：n/(2^k) = 1，也就是2^k = n，所以k = log₂n，所以二分查找的时间复杂度就是O(logn)。不管底数是2还是10，对数的底数只是一个常数系数，大O表示法里会直接省略，所以统一写成O(logn)。

很多人会觉得对数复杂度很抽象，其实你只要记住：只要每次循环问题规模折半(或者按固定比例缩小)，复杂度就是对数级别的，对数复杂度增长非常慢，哪怕n是100万，log₂n也才不到20，效率非常高。

规则三：多个输入规模要分开算

如果代码有多个不同的输入规模，那就要把多个规模都保留下来，不能合并。比如一个算法处理两个长度分别为m和n的数组，嵌套循环分别遍历两个数组，那复杂度就是O(m * n)，不能简化成O(n²)，因为m和n可能不一样大。

记住这三个规则之后，我们就可以快速分析绝大多数常见代码的时间复杂度了。

三、常用时间复杂度整理：从最优到最差，增长趋势一目了然

我们把常用的时间复杂度按效率从高到低排序，看看不同复杂度之间的增长差距：

大O表示法名称举例场景n=10时n=100时n=10000时

O(1)常数阶数组按索引访问、哈希表查询111

O(logn)对数阶二分查找、平衡树操作3714

O(n)线性阶遍历数组、单循环计算1010010000

O(nlogn)线性对数阶快速排序、归并排序、堆排序10*3=30100*7=70010000*14=140000

O(n²)平方阶冒泡排序、双重循环枚举10010000100000000

O(2ⁿ)指数阶暴力递归解斐波那契、子集枚举10241.2e30非常巨大

O(n!)阶乘阶全排列枚举所有情况3628800非常巨大不可想象

从这个表格就能非常清楚地看出差距：当n从10增长到10000的时候，O(1)和O(logn)几乎没变化，O(n)的执行次数也只是跟着线性增长，但O(n²)就已经到一亿次了，而O(2ⁿ)和O(n!)早就大到没办法运行了。这就是为什么我们说算法的时间复杂度决定了它能处理的数据规模，写代码的时候一定要尽量避开指数阶和阶乘阶的算法，能用多项式阶解决的问题就不要用暴力枚举。

举个实际的例子：你要给10万个整数排序，用O(n²)的冒泡排序，大概需要10次操作，普通计算机跑大概要几十秒甚至几分钟;但用O(nlogn)的快速排序，只需要大概10万 * 17 ≈ 170万次操作，一瞬间就能跑完，差距一目了然。

四、常见场景分析：几个典型例子帮你巩固方法

我们拿几个常见的代码例子，实战练习一下时间复杂度分析：

场景一：遍历一维数组找最大值

int findMax(int *arr, int n) {

int max = arr[0];

for (int i = 1; i < n; i++) {

if (arr[i] > max) {

max = arr[i];

}

}

return max;

}

整个代码只有一层循环，循环执行n-1次，最高阶是n，所以时间复杂度是O(n)，很好理解。

场景二：冒泡排序

void bubbleSort(int *arr, int n) {

for (int i = 0; i < n; i++) {

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

if (arr[j] > arr[j+1]) {

swap(arr[j], arr[j+1]);

}

}

}

}

很多人会觉得，冒泡排序第一趟循环n-1次，第二趟n-2次，最后一趟1次，总执行次数是(n-1)+(n-2)+...+1 = n(n-1)/2 = n²/2 - n/2，根据大O表示法的规则，我们忽略系数和低阶项，最后结果还是O(n²)，所以不管怎么优化，冒泡排序的时间复杂度都是平方级别的。

场景三：递归求斐波那契数列

int fib(int n) {

if (n <= 1) return n;

return fib(n-1) + fib(n-2);

}

这个递归写法非常经典，但效率极低。我们算一下它的时间复杂度：每一层递归都会分裂成两个新的递归，第一层1个，第二层2个，第三层4个……第n层就是2^(n-1)个，总调用次数就是1+2+4+...+2^(n-1) = 2^n - 1，所以时间复杂度是O(2ⁿ)，n稍微大一点就跑不动了。如果改成动态规划，用一个数组保存之前的结果，只需要循环一遍，时间复杂度就降到了O(n)，优化效果非常明显。

场景四：二分查找

我们之前已经分析过，二分查找每次折半，总循环次数是logn，所以时间复杂度是O(logn)，哪怕数组长度是1亿，最多也只需要循环27次就能找到目标，效率比从头到尾遍历O(n)高太多了。

场景五：快速排序

快速排序是最常用的排序算法，它的平均时间复杂度是O(nlogn)：每次我们选一个基准，把数组分成两部分，每一部分的规模加起来还是n，一共会分logn层，所以总操作次数就是n * logn，所以平均复杂度就是O(nlogn)，哪怕到了最坏情况每次都把数组分成1和n-1，最坏复杂度才是O(n²)，实际应用中几乎不会遇到这种情况，所以快速排序效率非常高。

五、容易踩坑的几个点：避坑指南帮你少出错

时间复杂度分析里有几个容易踩的坑，新手一定要注意：

第一个坑：把空间复杂度当成时间复杂度。很多人会混淆这两个概念，时间复杂度描述的是运行时间随输入规模的增长，空间复杂度描述的是额外占用内存随输入规模的增长，二者完全不是一回事。比如我们做数组反转，如果用额外数组保存结果，空间复杂度是O(n)，如果原地反转空间复杂度就是O(1)，但两种写法的时间复杂度都是O(n)。

第二个坑：递归的复杂度不会算。递归的复杂度其实很简单，你只要算一下总共递归调用了多少次，每次调用做了多少操作，乘起来就是了。比如上面的斐波那契递归，调用次数是2^n，每次操作是O(1)，所以总复杂度就是O(2^n)。再比如归并排序，每次把数组分成两半，一共logn层，每层处理所有n个元素，所以总复杂度就是O(nlogn)。

第三个坑：最好、最坏和平均复杂度分不清。我们平时说的时间复杂度一般都是最坏情况的复杂度，因为最坏情况是我们一定要面对的，比如你在数组里找目标，最坏就是要遍历整个数组，所以说复杂度是O(n)。但有些算法不同输入的复杂度差别很大，这时候我们会说平均复杂度，比如快速排序平均是O(nlogn)，最坏是O(n²)，这样描述就完整了。

第四个坑：忽略均摊复杂度。有些操作大部分时候是低复杂度，只有很少的时候是高复杂度，把高复杂度的成本均摊到所有操作上，均摊复杂度还是低的。最典型的例子就是动态数组扩容，比如C++的vector，每次满了就扩容成两倍，插入n个元素，只有logn次扩容需要移动所有元素，总的移动次数是n，均摊到每个插入操作上，均摊复杂度还是O(1)，所以我们说动态数组的插入操作均摊时间复杂度是O(1)。

时间复杂度分析其实一点都不难，核心就是抓住“增长趋势”四个字，记住“只看最高阶、忽略常数项、嵌套相乘、分支取最大”这几个简单规则，多分析几个常见的例子，很快就能熟练掌握。对于日常开发和面试来说，掌握我们本文讲的这些常用复杂度分析方法已经足够应对绝大多数场景。

理解时间复杂度的意义，不仅仅是为了应付面试，更重要的是让我们在写代码的时候养成“效率意识”：知道什么样的代码在处理大规模数据的时候会更快，知道不同算法的效率差距有多大，这样才能写出更高性能的程序，在遇到问题的时候选择最优的解法。