时间复杂度和空间复杂度
- 点击表格内对应链接跳转对应内容⬇️⬇️⬇️
| 作者主页 | 吃透C语言专栏 | 数据结构 | Gitee仓库 |
|---|
文章目录
- 一，算法效率
- 1 算法的复杂度
- 二，时间复杂度
- 1 时间复杂度定义
- 2 大O表示法核心规则
- 3 常见时间复杂度（从优到差排序）
- 三，空间复杂度
- 1 空间复杂度定义
- 2 递归与空间复杂度
一，算法效率
| 项目 | 具体说明 |
|---|---|
| 算法效率定义 | 评价算法性能优劣的核心指标，指算法在解决问题时对计算机系统资源的消耗程度。消耗的资源越少，算法效率越高。 |
| 时间效率 | 算法完成计算所消耗的时间资源，直接决定程序运行的快慢。 |
| 空间效率 | 算法运行过程中占用的内存、缓存等存储资源，决定程序对硬件存储的占用程度。 |
1 算法的复杂度
- 算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般
是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算
机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计
算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
二，时间复杂度
1 时间复杂度定义
| 定义维度 | 具体内容 |
|---|---|
| 核心含义 | 时间复杂度不是计算代码具体的执行秒数，而是衡量代码执行次数随数据量 n 增长的变化规律，使用大O表示法来描述这种趋势。 |
- 程序执行的时候用时间来计时，但是程序执行的时间和硬件和程序本身都有关系，但是我们的取的是程序本事执行的次数，执行的次数决定了程序执行时间的长短，和程序执行时间的快慢，所以时间复杂度计算的核心就是程序执行的次数
2 大O表示法核心规则
| 规则名称 | 规则说明与示例 |
|---|---|
| 只关注最高阶项 | 2n² + 3n + 1记为O(n²) |
| 忽略常数系数 | O(3n)简化为O(n) |
| 常数时间统一为 O(1) | 执行次数与数据量无关，统一记为O(1) |
- 当出现多种情况的话，我们取最坏情况的复杂度，比如说一个排序，如果最开始需要排序的数据原本就是排好的了，那么我们的时间复杂度就是O(1),但是如果数据原本就是乱的，那时间复杂度就是这个排序算法的时间复杂度，可能是O(n),既然有多种情况，可能是O(1),可能是O(n),我们取的是最坏的结果，也就是O(n)
3 常见时间复杂度（从优到差排序）
| 复杂度 | 名称 | 典型场景 | 增长特性 |
|---|---|---|---|
| O(1) | 常数阶 | 数组随机访问、变量赋值 | 不增长 |
| O(log n) | 对数阶 | 二分查找、二叉搜索树查询 | 极慢增长 |
| O(n) | 线性阶 | 数组遍历、单层循环 | 线性增长 |
| O(n log n) | 线性对数阶 | 归并排序、快速排序（平均） | 较快增长 |
| O(n²) | 平方阶 | 冒泡排序、双重循环 | 快速增长 |
| O(n³) | 立方阶 | 三重循环、Floyd 最短路算法 | 高速增长 |
| O(2ⁿ) | 指数阶 | 朴素递归斐波那契 | 爆炸增长 |
| O(n!) | 阶乘阶 | 全排列问题 | 超高速爆炸 |
三，空间复杂度
1 空间复杂度定义
- 衡量算法额外占用内存空间随数据规模 n 增长的趋势。
包括了算法创建的数组、对象、变量等额外空间（不计算原始输入本身占用的空间，除非要求“原地”算法）。依然使用大O表示法
- 总结：比如一个程序中，有一个数组，有一个for循环，那么这个数组所占的内存并不计入空间复杂度中算法额外占的空间，因为，空间复杂度明确了是算法额外占用的内存空间，也就是这个变量，必须是单独为了运行算法这个逻辑占用的空间，比如for循环中的初始化变量，判断变量，调整变量，这些变量就是为算法运行而服务的变量，也就是算法为了能够运行申请的空间，而刚刚说的数组，并不是为了支撑算法运行逻辑而申请的空间，是正常数据存储的空间，不是算法运行逻辑申请的空间
- 总结：空间是可能重复利用的，也就是说为了算法额外占用的空间，如果被重复利用，那这个空间只算一次，比如int a 申请了一块内存空间，我反复使用int a，我一直用的都是int a这一块空间，所以这一块空间只算一次
2 递归与空间复杂度
- 递归调用会占用调用栈空间，深度每增加一层，就需要分配新的栈帧。
如递归求阶乘 factorial(n) 递归深度为 n，空间复杂度就是 O(n)，而不是 O(1)。
- 总结：我们创建两个函数一个A函数，一个B函数，两个函数的实现是一样的，我们先调用A函数，再调用B函数，调用A函数的栈帧空间开辟以后，随着A函数调用结束，A函数的栈帧空间被回收，但是这一块空间的数据并没有被清楚，计算机中没有清除这个概念只有空间权限的概念，这块原本属于A的内存空间随着A函数的调用结束使用权限回归到了计算机，接下来B函数的调用，计算机给B开辟的空间就是刚刚回收的A的空间，这块申请过的空间再一次使用，只不过使用权给到了B函数，而调用的两次函数中，都是使用的同一块空间，所以被计入空间复杂度的空间调用，只有一次，因为两次调用用的都是同一块空间
- 点击表格内对应链接跳转对应内容⬇️⬇️⬇️
| 作者主页 | 吃透C语言专栏 | 数据结构 | Gitee仓库 |
|---|