01、时间空间复杂度分析
前言
在刷算法题中，我们主要有两个目标
- 通过所有测试用例
- 寻求效率最高的解法
第一个目标可以采用自己能想到的任何方法，也可以是暴力解法
第二个目标，则需要找到效率最高的解法，即运行时间最短，使用内存最小的写法。
最优解也是笔试时考察的点，所以我们在日常学习中，要尽可能的学习某个问题的最优解。所以能够会分析时间空间复杂度，是非常重要的一项技能
时间复杂度
先看一个例子
// 执行一次
int sum_a = 0;
sum_a = n * 1;
// 执行 n 次
int sum_b = 0;
for (int i = 1; i <= n; ++i) {
sum_b += 1;
}
// 执行 n*n 次
int sum_c = 0；
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
sum_c += 1;
}
}
上面的例子来看，sum_a 经过了 1 次运算，而 sum_b 经过了 n 次计算 ，而 sum_c 经过了 n*n 次计算，我们则可以写成
f(n) = 1;
f(n) = n;
f(n) = n*n;
其计算次数，随 n 的变化情况如下
-20251108220017780.(null))
根据上图可知，随着 n 的值增大，他们的计算次数的差异也就越大。
那么下面我们来看一个表格
| 次数 | f(n)=n+3 | f'(n)=n | g(n)=2n+1 | g'(n)=2n | k(n)=3n+1 | k'(n)=3n |
|---|---|---|---|---|---|---|
| n = 1 | 4 | 1 | 3 | 2 | 4 | 3 |
| n = 2 | 5 | 2 | 5 | 4 | 7 | 6 |
| n = 3 | 6 | 3 | 7 | 6 | 10 | 9 |
| n = 10 | 13 | 10 | 21 | 20 | 31 | 30 |
| n = 100 | 103 | 100 | 201 | 200 | 301 | 300 |
-20251108220018001.(null))
我们发现，随着 f(n) = n+3,在 n < 2 时，计算次数大于 g(n) = 2n+1,在 n = 2 时，两者计算次数相同，当 n > 2时，2n + 1 的计算次数恒大于 n+3
定义：对于两个函数 f(n) 和 g(n)，如果存在一个整数 N，使得对于 所有的 n > N,总是 f(n) > g(n),那么我们说 f(n) 的增长渐进快于 g(n)。这个定义可以结合上面的例子理解
另外我们发现，f(n) 和 f'(n) 对比，随着 n 的增大，后面相加常数，是不重要的
下面再来看一个例子
| n | f(n) = 6n+1 | f'(n)=n | g(n) = 3n^2+1 | g'(n)=n^2 |
|---|---|---|---|---|
| 1 | 7 | 1 | 4 | 2 |
| 2 | 13 | 2 | 13 | 4 |
| 3 | 19 | 3 | 28 | 9 |
| 10 | 61 | 10 | 301 | 100 |
| 100 | 601 | 100 | 30001 | 10000 |
| 1000 | 6001 | 1000 | 3000001 | 1000000 |
我们发现 当 n = 10 时，g(n) 的计算次数，就大于了 f(n)，而且去掉其相加的常数项，也不会影响其结果，而且就算去掉与 n 相乘的常数项，得到 g'(n), 对结果也没有什么影响，这时我们可以得到结论，与最高次数相乘的常数，也不重要
继续来看一个例子
| n | 2n^2+5n+5 | 2n^3+5n+5 |
|---|---|---|
| 1 | 12 | 12 |
| 2 | 23 | 31 |
| 3 | 38 | 74 |
| 10 | 255 | 2055 |
| 100 | 20505 | 2000505 |
| 1000 | 2005005 | 2000005005 |
最高项的，指数越大，其增长速率越快
那根据上面的例子，对增长速度，影响最大的是，最高次项的指数，指数越大，增长速度越快。
算法的时间复杂度，就是算法的时间量度，记作 T(n) = O(f(n))， 也就是随着 n 增大，算法执行时间的变化情况，在上面的例子中有提到，对增长速度影响最大的指标，根据时间复杂度的概念，上面的几个例子的时间复杂度，可以写成
O(1)，O(n), O(n^2)
下面详细说一下如何推导时间复杂度
- 忽略常数项
- 在运行函数中，只保留最高阶
- 忽略最高阶的系数
下面举个例子
f(n) = 4n^2 + 5n + 6
那按照上面提到的三条，则该计算函数的时间复杂度为 O(n^2)
对数阶
while (left < n) {
left = left * 2;
}
上面的代码中，我们发现， left 是成倍速接近 n 的，那么经历 2^x = n,则时间复杂度为 O(logn)
下面我们来看几个题目，看一下具体的时间复杂度是多少
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int ptr = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 0) {
swap(nums[i], nums[ptr]);
++ptr;
}
}
for (int i = ptr; i < n; ++i) {
if (nums[i] == 1) {
swap(nums[i], nums[ptr]);
++ptr;
}
}
}
};
可以理解为，遍历两遍数组，时间复杂度为 O(n)
class Solution {
public:
int minDepth(TreeNode *root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
int min_depth = INT_MAX;
if (root->left != nullptr) {
min_depth = min(minDepth(root->left), min_depth);
}
if (root->right != nullptr) {
min_depth = min(minDepth(root->right), min_depth);
}
return min_depth + 1;
}
};
这里我们需要对所有节点访问一次，故时间复杂度为 O(n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int first = 0; first < n; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int third = n - 1;
int target = -nums[first];
for (int second = first + 1; second < n; ++second) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while (second < third && nums[second] + nums[third] > target) {
--third;
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
这里我们确定 first 之后，还需要确定 second ，故时间复杂度为 O(n^2)
时间复杂度分析，需要多多练习，遇到题目时，先自己分析，理清自己的思考，然后再和答案对比，是一个不断总结的过程。
空间复杂度
算法的空间复杂度，用于衡量算法占用内存空间，随着数据量变大时的增长趋势。其实和咱们上面提到的时间一致，只需要将时间换成空间就好
算法执行时，分为，输入空间，暂存空间，输出空间
暂存空间又可以分为三个部分
- 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
- 栈帧空间：保存调用函数的上下文数据
- 指令空间：保存编译后的程序指令（忽略不计）
具体表现
暂时无法在飞书文档外展示此内容
空间复杂度统计时，主要考虑暂存数据，栈帧空间，输出空间
struct LinkNode {
int val;
Node *next;
Node(int x) : val(x), next(nullptr) {}
};
int func() {
cout << 123456 << " ";
return 0;
}
int test(int n) { // 输入数据,传参
const int temp_a = 0; // 暂存数据（常量）
int temp_b = 0; // 暂存数据（变量）
LinkNode* node = new LinkNode(0); // 暂存数据（对象）
int temp_c = func(); // 栈帧空间（调用函数）
return temp_a + temp_b + temp_c; // 输出数据
}
空间复杂度推算和时间复杂度推送一致，只不过是将操作次数，变为使用空间的大小。
下面我们来简要分析几个例子
int sum = 0;
void func(){
return 0;
}
for (int i = 0; i < n; ++i) {
func();
}
上面的例子，时间复杂度为 O(n), 空间复杂度为 O(1) 这是因为每轮中的 func() 都返回并释放了栈帧空间，因此空间复杂度仍为 O(1) 。
下面我们再看一个例子
void test(int n) {
if (n == 0) {
return;
}
return test(n - 1);
}
以上代码的时间复杂度为 O(n),空间复杂度也为 O(n), 该程序在跳出递归前，会不断压栈，会同时存在 n 个未返回的 test ，从而占用 O(n) 的栈帧空间。
下面继续看个示例
#include <vector>
#include <unordered_map>
#include <string>
// 定义链表节点类
class ListNode {
public:
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 函数用于展示线性空间复杂度
void test_linear(int n) {
// 长度为 n 的向量 nums，占用 O(n) 空间
std::vector<int> nums(n);
// 长度为 n 的向量 nodes，存储 n 个 ListNode 对象，占用 O(n) 空间
std::vector<ListNode> nodes;
for (int i = 0; i < n; i++) {
nodes.push_back(ListNode(i));
}
// 长度为 n 的哈希表 map，占用 O(n) 空间
std::unordered_map<int, std::string> map;
for (int i = 0; i < n; i++) {
map[i] = std::to_string(i);
}
}
在这个函数中，nums、nodes 和 map 分别占用 O(n) 的空间。根据空间复杂度的加法规则，总的空间复杂度为 O(n)。
下面继续看一个空间复杂度为 O(n^2) 的示例
#include <iostream>
#include <vector>
// 生成一个 n x n 的二维矩阵
std::vector<std::vector<int>> generateMatrix(int n) {
// 创建一个 n x n 的二维向量 matrix
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
// 遍历二维矩阵的每一个元素
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// 将矩阵元素初始化为其行索引和列索引的乘积
matrix[i][j] = i * j;
}
}
return matrix;
}
int main() {
int n = 3;
std::vector<std::vector<int>> result = generateMatrix(n);
// 输出二维矩阵
for (const auto& row : result) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
return 0;
}
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0)); 创建了一个 n×n 的二维向量 matrix，这个二维向量需要存储 n×n 个整数元素，因此它所占用的空间大小与 n2 成正比。
使用两层嵌套的 for 循环来遍历二维矩阵的每一个元素，并将其初始化为行索引和列索引的乘积。虽然循环内部的操作本身不占用额外的大量空间，但它是为了填充已经分配好的 n×n 大小的二维向量。
