【Python 数据结构 2.时间复杂度和空间复杂度】

Life is a journey

                          —— 25.2.28

一、引例：穷举法

1.单层循环

所谓穷举法，就是我们通常所说的枚举，就是把所有情况都遍历了的意思。

例：给定n（n ≤ 1000）个元素ai，求其中奇数有多少个

判断一个数是偶数还是奇数，只需要求它除上2的余数是0还是1，那么我们把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，这里需要遍历所有的数，这就是穷举

def JudgeNum(self, n: int, a: List[int]) -> int:count = 0for i in range(n):if a[i] % 2 == 1:count += 1return count

时间复杂度 O(n)

---

2.双层循环

例2：给定n（n ≤ 1000）个元素ai，求有多少个二元组（i，j），满足ai + aj是奇数（i < j）。

def JudgeNum(self, n: int, a[]: List[int]) -> int: count = 0for i in range(n):for j in range(i + 1, n):if (a[i} + a[j]) % 2 == 1:count += 1return count

时间复杂度 O(n^2)

---

3.三层循环

例3：给定n（n ≤ 1000）个元素ai，求有多少个三元组（i，j，k），满足ai + aj + ak是奇数（i < j < k）。

def JudgeNum(self, n: int, a: list[int]) -> int:count = 0for i in range(n):for j in range(i + 1, n):for k in range(j + 1, n):if (a[i] + a[j] + a[k]) % 2 == 1:count += 1return count 

时间复杂度 O(n^3)

随着循环嵌套的越多，时间消耗会越来越多，并且三个循环是乘法的关系，也就是遍历次数随着n的增加，呈现立方式的增长

---

4.递归枚举

例：给定n(n ≤ 1000)个元素ai 和 一个整数 k(k ≤ n)，求有多少个有序k数组，满足他们的和是偶数

我们需要根据k的不同，决定写几层循环，k的最大值为1000，也就意味着我们要写1000个if-else语句，显然，这样是无法接受的，比较暴力的做法是采用递归

---

二、时间复杂度

1.时间复杂度的表示法

在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随着 n 的变化情况而确定 T(n) 的数量级

算法的时间复杂度，就是算法的时间度量，记作：T(n)=O(f(n)) 用大写的 O 来体现算法时间复杂度的记法，我们称之为：大 O 记法

Ⅰ、时间函数

时间复杂度往往会联系到一个函数，自变量：表示规模，应变量：表示执行时间。

这里所说的执行时间，是指广义的时间，也就是单位并不是"秒"、"毫秒"这些时间单位，它代表的是一个"执行次数"的概念。我们用  f(n) 来表示这个时间函数。

Ⅱ、经典函数举例

在例1中，我们接触到了单层循环，这里的 n 是一个变量，随着 n 的增大，执行次数增大，执行时间就会增加，所以就有了时间函数的表示法如下：f(n) = n

这就是经典的线性时间函数

在例2中，我们接触到了双层循环，它的时间函数表示法如下：f(n) = n * (n - 1) / 2

这是一个平方级别的时间函数

在例3中，我们接触到了三层循环，它的时间函数表示法如下：f(n) = n * (n - 1) * (n - 2) / 6

这是一个立方级别的时间函数

---

2.时间复杂度

一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

并且我们有一个更加优雅的表示法，即：T(n)=O(f(n))，其中 O 念成 大O

1) 当 f(n) = n，我们称这个算法拥有线性时间复杂度，记作 O(n);

2) 当 f(n) = n * (n-1) / 2，我们称这个算法拥有平方级时间复杂度，记作 O(n^2);

3) 当 f(n) = n * (n-1) * (n-2) / 6,我们称这个算法拥有立方级的时间复杂度，记作 O(n^3);

这时候我们发现，f 的函数可能很复杂，但是 O 表示的函数往往比较简单，它舍弃了一些"细节“

---

3.高阶无穷小

如果 lim(β / α) = 0，则称 ”β 是比 α较高阶的无穷小“

例：f(n) = n * (n - 1) / 2

共两部分组成，一部分是 n ^ 2 的部分，另一部分是 n 的部分，显而易见，一定是 n ^ 2，相对于 n ^ 2 来说，n 可以忽略不计

随着 n 的增长，线性的部分增长已经跟不上平方部分，这样，线性部分的时间消耗相对于平方部分来说已经”微不足道“，所以我们直接忽略，于是就有时间复杂度表示如下：

T(n) = O(f(n))

        = O(1/2 * n ^ 2 - 1 / 2 * n)

        = O(1/2 * n ^ 2)

        = O(n ^ 2)

所以，它的时间复杂度就是O(n ^ 2)了

---

4.简化系数

发现上述的公式推到的过程中，将 n ^ 2 前面的系数 1/2 去掉了，这是由于 时间复杂度描述的更多的是一个数量级，所以尽量减少干扰项，对于两个不同的问题，可能执行时间不同，但是我们可以说他们的 时间复杂度 是一样的

---

三、常见的时间复杂度

1.常数阶

max = 1024
def getMax() -> int:return max  

没有循环，是常数时间，表示为O(1)

---

2.对数阶

例4：给定n(n ≤ 10000)个元素的有序数组 ai 和 整数 v，求 v 在数组中的下标，不存在则输出 -1

这个问题是一个常见的查询问题，我们可以用O(n)的算法遍历整个数组，然后去找 v 的值

当然，也有更快的方法，注意到题目中的条件，数组 ai 是有序的，所以我们可以利用二分查找来实现

def bin(n: int, a: List[int], v:int) -> int:left = 0,right = n - 1mid = 0while left <= right:mid = (left + right) // 2if a[mid] < v:left = v + 1elif a[mid] > v:right = v - 1else:return midreturn -1

这是一个二分查找的实现，时间复杂度为O(logn)

每次相当于把n切半，即：

n -> n / 2 -> n / 4 -> … -> n / 2 ^ k -> … -> 0

f(n) = O(n) = O(k) = O(logn)

---

3.根号阶

例5：给定一个数 n(n ≤ 10 ^ 9)，问 n 是否是一个素数（素数的概念：除了1和它本身，没有其他因子）

基于素数的概念，我们可以枚举所有 i 属于[2, n)，看能否整除 n，一旦能整除，代表找到了一个银子，则不是素数，当所有数枚举完还没找到，他就是素数

但是这样做，显然效率太低，我们进行一些思考，得到如下算法：

import mathdef isPrime(n: int) -> bool:if n <= 1:return Falsesqrtn = math.sqrt(n)for i in range(2, sqrtn + 1):if n % i == 0:return Falsereturn True

这个算法的时间复杂度为：O(根号n)

为什么只需要枚举 根号n 以内的数呢？

因为一旦有一个因子 s，必然有另一个因子 n / s，它们之间必然有一个大小关系，无论是 s ≤ n / s，还是 n / s ≤ s，都能通过两边乘上 s 得出：

比根号n小的数中，如果没有这样一个因子，则比根号n大的数中也不会存在这样一个因子

---

4.线性阶

例1中，我们接触到了单层循环，这里的 n 是一个变量，随着 n 的增大，执行次数增大，执行时间就会增加，所以就有了时间函数的表示法如下：f(n) = n

---

5.线性对数阶

例6：给定n(n ≤ 100000)个元素 ai，求满足 ai + aj = 1024 的有序二元组(i, j)有多少对

我们可以先对所有元素 ai 按照递增排序，然后枚举 ai，并且在[i + 1, n)范围内查找是否存在 ai + aj = 1024

def Find(n: int, a: List[int]) -> int:count = 0sort(a)for i in range(n):j = 1024 - a[i]left, right = i + 1, n - 1while left <= right:mid = left + (right - left) // 2if a[mid] == target:count += 1breakelif a[mid] < taegrt:left = mid + 1else:right = mid - 1return count

 f(n) = O(n * logn) = O(nlogn)

---

6.多项式阶

多项式的含义是函数 f(n) 可以表示成如下形式：

所以 O(n^5)、O(n^4)、O(n^3)、O(n^2)、O(n)都是多项式时间

---

7.指数阶 

例7：给出n(n ≤ 15)个点，以及每两个点之间的关系（连通还是不连通），求一个最大的集合，使得在这个集合中都连通

这是求子集的问题，由于最多只有 15 个点，我们就可以枚举每个点选或者不选，总共 2^n 种情况，然后再判断是否满足题目中的连通性，这个算法时间复杂度为 O(n ^ 2 * 2 ^ n)；

---

8.阶乘阶

例8：给定n(n ≤ 12)个点，并且给出任意两点间的距离，求从 s 点开始经过所有点回到 s 点的距离的最小值

这个问题就是典型的暴力枚举所有情况求解，可以把这些点当成是一个排列，所以排列方案数为： n！

---

四、如何判断时间复杂度

1.标准

首先，我们需要一个标准，也就是总的执行次数多少合适

我们把其定义为 S = 10 ^ 6

2.问题规模

有了标准以后，我们还需要知道问题规模，也就是O(n)中的n

3.套公式

然后就是凭感觉套公式了

        当 n < 12 时，可能是需要用到阶乘级别的算法，即 O(n!)

        当 n < 16 时，可能是需要状态压缩的算法，比如 O(n ^ 2)、O(n * 2 ^ n)、O(n ^ 2 * 2 ^ n)

        当 n < 30 时，可能是需要 O(n ^ 4)的算法，因为 30 ^ 4 差不多接近 10 ^ 6

        当 n < 100 时，可能是需要 O(n)的算法，因为 1003= 106

        当n < 1000 时，可能是需要 O(n ^ 2)的算法，因为 1000 ^ 2 = 10 ^ 6

        当n < 100000 时，可能是需要 O(n * log2n)、O(n * (log2n) ^ 2)的算法

        当n < 1000000 时，可能是需要 O(根号n)、O(n)的算法

---

五、空间复杂度

        空间复杂度是指算法在执行过程中所需的额外存储空间。这包括算法在运行时使用的变量、数组、链表 等数据结构所占用的内存空间。它和算法的时间复杂度一起，是衡量算法性能的重要指标之一。

        在算法设计中，我们通常希望尽可能地降低空间复杂度，以减少内存的使用，提高算法的效率。然而，在某些情况下，为了实现算法的功能，可能需要使用更多的存储空间。

---

六、常见数据结构的空间复杂度

1.顺序表：O(n)，其中 n 是顺序表的长度

2.链表：O(n)，其中 n 是链表的长度

3.栈：O(n)，其中 n 是 栈的最大深度

4.队列：其中 n 是队列的最大长度

5.哈希表：O(n)，其中 n 是哈希表中元素的数量

6.树：O(n)，其中 n 是树的节点数量

7.图：O(n + m)，其中 n 是图中顶点的数量，m 是图中边的数量

---

七、空间换时间

通常使用额外空间的目的，就是为了换取时间上的效率，也就是我们常说的 空间换时间。

最经典的空间换时间就是动态规划，例如求一个斐波那契数列的第 n 项的值，如果不做任何优化就是利用循环进行计算，时间复杂度 (n)，但是如果引入了数组，将计算结果预先存储在数组中，那么每次询问只需要 O(1) 的时间复杂度就可以得到第 n 项的值，而这时，由于引入了数组所以空间复杂度就变成了 O(n)。