数据结构：时间复杂度（Time Complexity）和空间复杂度（Space Complexity）

目录

什么是时间复杂度？

如何表示时间复杂度？

为什么需要时间复杂度？ 

用几个例子理解

怎么分析代码的时间复杂度？

什么是空间复杂度？

举例理解

---

什么是时间复杂度？

时间复杂度是用来衡量一个算法“运行时间随输入规模增长的速度”的指标。

我们关心的是：
➡ 当输入规模 n 越来越大时，程序运行时间变快还是变慢？变慢得有多快？

但注意：
我们不是计算具体运行时间（秒），而是研究增长趋势（数量级）！

比如：

• 输入 10 个元素花 1ms，100 个元素花 100ms：说明时间增长很快。

• 输入 10 个元素花 1ms，100 个元素花 2ms：说明增长很慢，很高效。

如何表示时间复杂度？

我们通常用大 O 表示法（Big-O Notation）来表示时间复杂度，比如：

• O(1) 常数级

• O(log⁡n)对数级

• O(n)线性级

• O(nlog⁡n) 线性对数级

• O(n^2)平方级

• O(2^n)、O(n!)指数、阶乘级（非常慢）

这些从快到慢大致排序为：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

为什么需要时间复杂度？ 

能预测程序是否能处理大数据。 

• 比如O(n^2)的程序在 n = 10^5时已经跑不动了；

• 而 O(nlog⁡n) 在 n = 10^6 时依然很快。

 能比较不同算法的效率。

选择排序是 O(n^2)，归并排序是 O(nlog⁡n)，在大数据面前差别巨大。

用几个例子理解

1. O(1)：常数级

int a = 5;
int b = a + 3;

 不管你输入多大，只执行几条语句，时间不随输入增长。

2. O(n)：线性级

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

 循环执行 n 次，输入增加一倍，运行时间也大致增加一倍。

3. O(n²)：平方级 

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

嵌套循环，每层都跑 n 次，总运行次数为 n×n = n^2。

4. O(log n)：对数级（如二分查找） 

int binarySearch(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) return mid;else if (nums[mid] < target) l = mid + 1;else r = mid - 1;}return -1;
}

 每次把搜索区间减半，只需要约 log⁡2n 次判断。

怎么分析代码的时间复杂度？

你可以遵循以下步骤：

1. 看循环嵌套层数

   一层是 O(n)，两层是 O(n^2)，三层是 O(n^3)

2. 注意递归的调用树

   如归并排序是 T(n)=2T(n/2)+O(n) → O(nlog⁡n)

3. 看是否有减半、指数增长、全排列等模式

 

 

---

什么是空间复杂度？

空间复杂度（Space Complexity）是衡量一个算法在运行过程中临时占用多少内存空间的指标。

它回答的问题是：

如果输入规模是 n，算法为了运行，需要开辟多大的“额外空间”？

⚠️ 注意：

• 不包括输入本身所占的空间，我们关心的是额外的空间使用。

• 就像时间复杂度关注“运算量增长”，空间复杂度关注“内存占用增长”。

举例理解

1. O(1)：常数空间（最优）

int sum = 0;
for (int i = 0; i < n; i++) {sum += arr[i];
}

这里只是用了一些变量（sum, i），无论 n 多大，占用空间都是常数级。

2. O(n)：线性空间 

vector<int> res(n);
for (int i = 0; i < n; i++) {res[i] = arr[i] * 2;
}

 开了一个和输入一样大的数组 res，所以空间复杂度是 O(n)。

3. O(n²)：二维数组 

int matrix[n][n];

 每个维度都是 n，所以总共是n×n=n2 个元素，空间复杂度是 O(n²)。

4. 递归调用带来的空间 

int factorial(int n) {if (n == 1) return 1;return n * factorial(n - 1);
}

 每次递归调用都要占用一次调用栈帧，调用 n 层，就要O(n) 空间。

有些递归算法虽然时间复杂度是 O(n)，但如果用了“尾递归”或“迭代替代递归”，可以把空间优化到 O(1)。