数据结构：2.时间复杂的和空间复杂度
【目标】
1.如何衡量一个算法的好坏
2.复杂度
3.算法效率
1.如何衡量一个算法的好坏？
1.1 两大核心指标（理论层面）
| 指标 | 问的问题 | 表示法 | 例子 |
|---|---|---|---|
| 时间复杂度 | 数据量增大，耗时怎么增长？ | 大O表示法 | O(n) 比 O(n²) 好 |
| 空间复杂度 | 数据量增大，内存怎么增长？ | 大O表示法 | O(1) 比 O(n) 好 |
目前来讲，时间复杂度更重要，原因如下：
早期（大约80-90年代）：内存是金子。当时用KB（千字节）甚至Byte（字节）来算钱。一个算法能省1KB内存，可能就意味着能多运行一个程序。所以，当时空间复杂度是王，会用时间去换空间。
现在（最近20年）：内存变成了白菜。你花几百块钱就能买到16GB、32GB的内存，而CPU的性能提升却遇到了物理瓶颈。用户的耐心也越来越有限，一个网页加载超过2秒就可能被关闭。所以现在，时间复杂度是王，会用空间去换时间。
1.2 两个实际考量（工程层面）
有时候理论好的算法，实际中不一定用。
| 指标 | 问的问题 | 例子 |
|---|---|---|
| 正确性 | 结果对不对？ | 排序算法必须真的排好序 |
| 可读性 | 别人能看懂吗？ | 宁愿用简单的冒泡排序，也不用晦涩的堆排序（如果数据量小） |
1.3 数据规模
在实际开发过程中，判断一个算法的好坏并不是单一的根据某一特性进行判断，而是要根据不同的数据规模选择合适的算法。比如：
对一组数据进行排序：
| 数据规模 | 你会怎么选 | 理由 |
|---|---|---|
| 10条 | 随便写，甚至手写冒泡 | 可读性最重要，不用动脑 |
| 1万条 | Arrays.sort()（快排） | 时间重要，但Java已经帮你优化好了 |
| 1亿条 | 外部排序 + 并行处理 | 时间压倒一切，空间也得精打细算 |
1.4 总结
衡量一个算法的好坏，由时间复杂度、空间复杂度、正确性、可读性这四个方面进行评判。但是评判的前提是确定算法的业务场景、公司需求、数据规模等等。
2.复杂度
2.1 大O的渐进表示法
在计算时间复杂度和空间复杂度的时候，有很多情况下我们都不能精确的对其进行计算，所以我们用估算值来当作结果对其进行评判，这里我们就用到大O的渐进表示法：
- 用常数1取代运行时间中的所有常数项。（如果常数项为0，那么就不用1来进行取代）
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。
大O的渐进表示法描述的是“当 n 很大时的趋势”。如果 n 本身就很小，大O的意义不大，选简单的、可读性好的算法就行；数据量大时，大O是生死线。
2.2 时间复杂度
2.2.1 时间复杂度的概念
在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。
但是在每个程序确定之前，我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。由于一个算法所花费的时间与其中语句的执行次数成正比例，算法中的执行次数最多、复杂度最高的那段代码的执行次数，为算法的时间复杂度。
2.2.2 常见的时间复杂度计算举例
【示例一】
// 计算func2的时间复杂度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;//语句一
}
int M = 10;
while ((M--) > 0) {
count++;//语句二
}
System.out.println(count);
}
由于count++是执行次数最多、复杂度最高的语句，所以我们计算他的时间复杂度作为算法的时间复杂度。
语句一：执行 2*n 次
语句二：执行 10 次
那么总共的执行次数就是 2*n + 10 次
下面我们采取大O的渐进表示法对其进行计算。
- 2*n + 10 ——> 2*n + 1
- 2*n + 1 ——> 2*n
- 2*n ——> n
所以我们计算出来的结果就是：O(n)
【示例二】
// 计算binarySearch的时间复杂度？
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;
}
由于循环体内部的比较和赋值是执行次数最多、复杂度最高的语句，所以我们计算他的时间复杂度作为算法的时间复杂度。
每循环一次，搜索范围缩小一半
初始范围：n个元素
第1次循环后：剩余n/2
第2次循环后：剩余n/4
第k次循环后：剩余n / (2^k) == 1
那么也就是说我们在k次循环中总共执行了：log₂ n
下面我们采取大O的渐进表示法对其进行计算。
log₂ n —— 没有加法常数，不变
保留最高阶项 —— 就是 log₂ n
去除系数（系数已经是1）——log n
所以我们计算出来的结果就是：O(log n)
2.3 空间复杂度
2.3.1 空间复杂度的概念
空间复杂度是对一个算法在运行过程中，空间复杂度是临时占用存储空间大小的量度，只算额外占用的、辅助性质的临时内存（也就是说除了输入数据所占用的存储空间的大小，其他的都算）（注意：这里的空间复杂度的计算方法是在实际开发中的，在学术上并不是这样规定） 。空间复杂度不是程序占用了多少byte的空间，因为这个也没太大意义，所以空间复杂度算的是中间变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
2.3.2 常见的空间复杂度的计算举例
【示例一】
int sum(int[] arr) {
int total = 0; // 1个变量
for (int i = 0; i < arr.length; i++) {
total += arr[i]; // 没有额外数组
}
return total;
}
可以看出，我们额外的变量只有 i 和 total 这两个变量，所以来说额外变量就是 2 个
那么根据大O的渐进表示法计算出空间复杂度为：O(1)
【示例二】
int[] copyArray(int[] arr) {
int[] newArr = new int[arr.length]; // 第1步
for (int i = 0; i < arr.length; i++) { // 第2步
newArr[i] = arr[i];
}
return newArr; // 第3步
}
可以看出，我们额外的变量有 newArr这个数组 和 i 这个变量，所以说额外变量应该是 n + 1个
那么根据大O的渐进表示法计算出的空间复杂度为：O(n)
3.算法效率
算法效率分为两种：时间效率和空间效率。
•时间效率 = 算法实际运行消耗的真实时间
•空间效率 = 算法实际运行消耗的真实内存（总内存）
以下是DeepSeek关于时间效率和空间效率相关细节的回答：
“对于一个需求有不同的算法，我们会根据正确性、可读性、时间复杂度、空间复杂度四点来评判算法。”
✅正确。这是四个维度。
“大多数情况下，我们更看重时间效率和空间效率。”
✅正确。在正确性和可读性满足基本要求后，效率和资源占用通常是核心关注点。
“所以我们会根据时间复杂度和空间复杂度这两个指标筛选掉明显很差的。”
✅正确。比如时间复杂度 O(n²) 的直接淘汰，空间复杂度 O(n²) 的直接淘汰。
“但是这两个指标不能进行精确筛选。”
✅正确。因为时间复杂度和空间复杂度（常用的大O的渐进表示法）是理论趋势，不是具体数值。同为 O(n) 的两个算法，实测可能差 10 倍。
“所以我们引入了效率这个理论概念，理论与实践结合，在实践中进行更深层次的筛选。”
✅正确。先用复杂度（理论）筛掉明显不行的，再用效率（实测）从剩下的里挑最好的。