【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 = 0
for i in range(n):
if a[i] % 2 == 1:
count += 1
return 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 = 0
for i in range(n):
for j in range(i + 1, n):
if (a[i} + a[j]) % 2 == 1:
count += 1
return 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 = 0
for 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 += 1
return 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 - 1
mid = 0
while left <= right:
mid = (left + right) // 2
if a[mid] < v:
left = v + 1
elif a[mid] > v:
right = v - 1
else:
return mid
return -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 math
def isPrime(n: int) -> bool:
if n <= 1:
return False
sqrtn = math.sqrt(n)
for i in range(2, sqrtn + 1):
if n % i == 0:
return False
return 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 = 0
sort(a)
for i in range(n):
j = 1024 - a[i]
left, right = i + 1, n - 1
while left <= right:
mid = left + (right - left) // 2
if a[mid] == target:
count += 1
break
elif a[mid] < taegrt:
left = mid + 1
else:
right = mid - 1
return countf(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)。