2.算法效率的核心密码：时间复杂度和空间复杂度详解

目录

一、为什么要关心算法效率？

如何衡量一个算法的好坏？

二、时间复杂度：算法到底跑了多久？

2.1 时间复杂度的本质

2.2 大O渐进表示法

2.3 最好、平均、最坏情况

2.4 常见时间复杂度计算实战

实例1：单层循环 + 常数操作

实例2：两个未知数的双层循环

实例3：常数次操作

实例4：冒泡排序

实例5：二分查找

实例6：阶乘递归

实例7：斐波那契递归（经典反面教材）

三、空间复杂度：算法占了多少内存？

3.1 空间复杂度的本质

3.2 空间复杂度计算实战

实例1：冒泡排序

实例2：斐波那契数列（非递归版本）

实例3：阶乘递归

四、时间复杂度与空间复杂度的权衡

五、常见时间复杂度对比

六、如何提升算法效率的分析能力？

七、写在最后

写在前面：本文是基于数据结构中关于时间复杂度和空间复杂度章节的学习整理，结合了个人理解和代码实践。文中所有示例均经过重新编写和验证，旨在帮助初学者建立对算法效率的正确认知。如需深入学习，建议配合原版教材或官方文档使用。

一、为什么要关心算法效率？

还记得我们之前聊过的Java集合框架吗？ArrayList和LinkedList同样是List接口的实现类，为什么在不同场景下性能差异巨大？这背后就是算法效率在起作用。

举个最简单的例子：假设你要在一个包含100万个元素的列表中查找某个值。

• 顺序查找：运气不好时需要比较100万次

• 二分查找：最多只需要比较20次

这就是算法效率带来的差距——同样的功能，不同的实现方式，性能可能天差地别。

如何衡量一个算法的好坏？

我们先来看一个经典的斐波那契数列递归实现：

public static long fib(int N) { if (N < 3) { return 1; } return fib(N - 1) + fib(N - 2); }

这段代码看起来简洁优雅，但当你尝试计算fib(50)时，会发现它慢得令人崩溃。为什么？因为它做了大量的重复计算。

衡量算法好坏的两个核心指标就是：时间复杂度和空间复杂度。

二、时间复杂度：算法到底跑了多久？

2.1 时间复杂度的本质

时间复杂度并不是指算法实际的运行时间（因为不同机器、不同语言、不同输入都会影响），而是算法中基本操作的执行次数与输入规模之间的关系。

简单来说：输入规模越大，算法要做的操作越多，这个"多多少"就是时间复杂度关心的核心问题。

2.2 大O渐进表示法

在实际工程中，我们并不需要精确计算算法的执行次数，而是关注其增长趋势。这就是大O表示法的作用。

推导大O阶的三个原则：

1. 用常数1取代运行时间中的所有加法常数

2. 只保留最高阶项

3. 如果最高阶项存在且系数不为1，去掉系数

举个例子，假设一个算法的基本操作执行次数为：

F(N)=N^2+2N+10

根据大O表示法：

• 当N很大时，2N+10相对于 N^2可以忽略不计

• 所以时间复杂度为 O(N^2)

2.3 最好、平均、最坏情况

同一个算法在不同输入下的表现可能完全不同。以在数组中查找某个值为例：

• 最好情况：第一个就是要找的元素，1次找到 → O(1)

• 最坏情况：最后一个才是要找的元素，N次找到 → O(N)

在实际开发中，我们通常关注最坏情况，因为这代表了算法的性能下限。

2.4 常见时间复杂度计算实战

实例1：单层循环 + 常数操作

void func2(int N) { int count = 0; // 循环2N次 for (int k = 0; k < 2 * N; k++) { count++; } // 常数次操作 int M = 10; while ((M--) > 0) { count++; } System.out.println(count); }

分析：基本操作执行了2N + 10次，根据大O表示法，时间复杂度为O(N)。

实例2：两个未知数的双层循环

void func3(int N, int M) { int count = 0; for (int k = 0; k < M; k++) { count++; } for (int k = 0; k < N; k++) { count++; } }

分析：执行了M + N次，两个未知数无法确定谁更大，时间复杂度为O(M + N)。

实例3：常数次操作

void func4() { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count); }

分析：无论输入规模多大，永远执行100次，时间复杂度为O(1)。

实例4：冒泡排序

void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { swap(array, i - 1, i); sorted = false; } } if (sorted) { break; } } }

分析：

• 最好情况（数组已经有序）：执行N次 → O(N)

• 最坏情况（数组完全逆序）：执行N*(N-1)/2次 → O(N²)

实际中我们关注最坏情况，所以时间复杂度为O(N²)。

实例5：二分查找

int binarySearch(int[] array, int value) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + ((end - begin) / 2); if (array[mid] < value) { begin = mid + 1; } else if (array[mid] > value) { end = mid - 1; } else { return mid; } } return -1; }

分析：每次查找都将范围缩小一半，经过log₂N次查找后找到目标。时间复杂度为O(log N)。

💡小技巧：你可以把二分查找想象成猜数字游戏——每次猜中间值，然后根据提示"大了"或"小了"，排除掉一半的数字。这样理解起来会更直观。

实例6：阶乘递归

long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }

分析：递归调用了N次，每次执行常数操作。时间复杂度为O(N)。

实例7：斐波那契递归（经典反面教材）

int fibonacci(int N) { return N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2); }

分析：这是一个指数级的递归调用，每次调用会产生两个新的调用，形成一棵深度为N的二叉树。总调用次数约为 2^N次，时间复杂度为O(2^N)。

这也是为什么用递归计算fib(50)会慢到让人怀疑人生的原因——它需要执行大约 250次操作！

三、空间复杂度：算法占了多少内存？

3.1 空间复杂度的本质

空间复杂度衡量的是算法在运行过程中临时占用的存储空间大小。注意，这里说的是"临时"——即除了输入数据本身之外，额外需要的空间。

在计算机发展早期，内存非常珍贵，空间复杂度曾是重中之重。但如今，随着硬件成本的降低，我们通常更关注时间复杂度。不过在某些场景下（如嵌入式系统、移动设备），空间复杂度依然很重要。

3.2 空间复杂度计算实战

实例1：冒泡排序

void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; // 1个变量 for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { swap(array, i - 1, i); sorted = false; } } if (sorted) { break; } } }

分析：只使用了常数个额外变量（end、sorted、i等），不随输入规模变化。空间复杂度为O(1)。

实例2：斐波那契数列（非递归版本）

int[] fibonacci(int n) { long[] fibArray = new long[n + 1]; fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n; i++) { fibArray[i] = fibArray[i - 1] + fibArray[i - 2]; } return fibArray; }

分析：创建了一个大小为n+1的数组，空间随输入规模线性增长。空间复杂度为O(N)。

实例3：阶乘递归

long factorial(int N) { return N < 2 ? N : factorial(N - 1) * N; }

分析：递归调用N次，每次调用会在栈上创建一个栈帧，每个栈帧占用常数空间。总共占用N个栈帧，空间复杂度为O(N)。

四、时间复杂度与空间复杂度的权衡

在算法设计中，时间和空间往往是一对矛盾体。有时候我们可以用空间换时间，也可以用时间换空间。

典型例子：斐波那契数列

• 递归版本：时间复杂度 O(2^N)，空间复杂度 O(N)

• 迭代版本：时间复杂度 O(N)，空间复杂度 O(1)

显然，迭代版本无论在时间还是空间上都优于递归版本。这也告诉我们：写代码时不要盲目追求"优雅"的递归，要考虑实际性能。

五、常见时间复杂度对比

六、如何提升算法效率的分析能力？

1. 多动手画图：特别是递归调用、循环嵌套这种抽象的结构，画图能让思路清晰很多

2. 刻意练习：在LeetCode或牛客网上做题时，养成先分析时间空间复杂度的习惯

3. 阅读优秀源码：JDK源码中有大量精妙的实现，值得反复品味

4. 总结归纳：遇到新的算法模式时，记下来并与已知的模式做对比

七、写在最后

时间复杂度和空间复杂度是算法分析的基石，也是面试中绕不开的话题。理解它们不仅能帮你在面试中脱颖而出，更能让你在日常开发中写出更高效的代码。

下一篇文章，我们将把这些知识应用到集合框架的源码分析中，看看ArrayList和LinkedList各自的性能特点是如何由它们的底层数据结构决定的。

如果你觉得这篇文章有帮助，欢迎点赞收藏。有任何疑问，欢迎在评论区交流探讨！

注：本文为个人学习总结，文中示例均为独立编写。建议读者在学习过程中结合实际代码运行验证，加深理解。