通过什么来衡量一个算法的好坏呢，那就是时间复杂度和空间复杂度。实现相同功能但时间和空间复杂度更优的算法是更优的算法，算法需要优化也可以从时间或者空间的复杂度的角度来考虑。
时间复杂度主要衡量一个算法执行所需的时间长短，具体来说，如果一个算法的时间复杂度是O(n)，那么这意味着当输入规模增加时，算法的执行时间大致上会以线性方式增加。常见的时间复杂度级别有O(1)（常数时间）、O(n)（线性时间）、O(n^2)（平方时间）、O(log n)（对数时间）等。
空间复杂度主要衡量算法执行过程中所需的额外空间（不包括输入数据所占用的空间）空间复杂度关注的是算法在执行过程中所需的临时存储空间大小，这包括变量、数据结构以及递归调用栈等所占用的空间。一个算法的空间复杂度越低，它在执行时占用的内存就越少。
简单总结就是代码运行所花时间和运行占用的空间大小。
1 时间复杂度
上面说到时间复杂度是运行代码所花的时间的长短，但是代码还未运行怎么能预知代码运行所花时间的长短呢，这里就提出了一个概念渐进式时间分析。
这里举个例子
比如有一个10cm的油条，每3分钟吃1cm需要多久能吃完呢？
答案是30分钟
如果一个ncm的油条，每3分钟吃1cm需要多久能吃完呢？
答案是3n分钟，用一个函数表示即T(n) = 3n
这个的3是一个常量，如果n足够大的话3对它的影响很小，所以T(n) = n
也就是说时间复杂度并不是真正的代码执行的长度，而是根据代码的执行次数推算出来的执行长度。
list_a = [1, 2, 3, 4, 5, 6]
total = 0
for i in list_a:
for j in list_a:
total += 1
print("执行的总次数:", total)
"""
执行的总次数: 36
"""
如上所示，列表的长度为6双层循环之后总的执行次数为36，如果长度为n的话就能推算出算法的时间复杂度为n^2，在时间复杂度中如果计算出有多项式一般取最大项。
常见的时间复杂度有
常数量级：T(n) =O(1)
指数量级：T(n) =O(logn)
线性量级：T(n)=O(n)
平方量级：T(n) =O(n^2 )
O(1)<O(logn)<O(n)<O(n^2)
2 空间复杂度
而空间复杂度就是执行代码所需要的成本，执行代码是否需要额外申请空间。
students = {
"小明": 10,
"小红": 11,
"小白": 12,
"小黑": 11,
}
age_map = {}
for age in students.values():
if age in age_map:
age_map[age] += 1
else:
age_map[age] = 1
print(age_map)
"""
{10: 1, 11: 2, 12: 1}
"""
如上图，计算学生年龄的分布需要申请一个额外字典来保存来保存年纪信息。字典的长度和学生列表长度有关空间复杂度为O(n)
时间复杂度为O(n)，如果分配的额外空间是一个二维的则空间复杂为O(n^2)。
还有一个比较特殊场景，递归的时候并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。“方法调用栈”包括进栈和出栈两个行为。当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。
当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。
def fibonacci(n):
if n <= 0:
return "输入错误！n应该是正整数。"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# 示例：计算斐波那契数列的第10项
print(fibonacci(10)) # 输出：55
如上所示，计算n项的斐波那契需要将n-1项压入栈，再运行时再出栈，空间的复杂度为O(n)
常见的空间复杂度按照从低到高的顺序，包括O(1)、O(n)、O(n 2)等
3 时间复杂度和空间复杂度的取舍
人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。
正所谓鱼和熊掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。
在算法设计和优化中，时间复杂度和空间复杂度的取舍是一个重要的考虑因素。这通常取决于具体的应用场景、硬件限制以及性能要求。在某些情况下，我们可能更倾向于优化时间复杂度，而在其他情况下，空间复杂度可能更为重要。
示例 1：查找列表中的元素
方法 1：线性搜索（低空间复杂度，线性时间复杂度）
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i # 返回元素的索引
return -1 # 如果没有找到元素，返回-1
# 示例：查找元素5在列表中的索引
numbers = [1, 3, 5, 7, 9]
index = linear_search(numbers, 5)
print(index) # 输出：2
这个方法的时间复杂度是O(n)，因为它需要遍历整个列表。空间复杂度是O(1)，因为它只需要固定数量的额外空间。
方法 2：使用集合（高空间复杂度，平均时间复杂度接近常数）
def set_search(lst, target):
num_set = set(lst)
return target in num_set
# 示例：检查元素5是否在集合中
numbers = [1, 3, 5, 7, 9]
is_present = set_search(numbers, 5)
print(is_present) # 输出：True
虽然这个方法返回的是一个布尔值而不是索引，但它展示了如何使用集合来加速查找。集合的查找平均时间复杂度接近O(1)，但创建集合的过程需要O(n)的时间复杂度，并且集合本身需要O(n)的空间复杂度来存储所有元素。
