时间复杂度和空间复杂度

通过什么来衡量一个算法的好坏呢，那就是时间复杂度和空间复杂度。实现相同功能但时间和空间复杂度更优的算法是更优的算法，算法需要优化也可以从时间或者空间的复杂度的角度来考虑。

时间复杂度主要衡量一个算法执行所需的时间长短，具体来说，如果一个算法的时间复杂度是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)的空间复杂度来存储所有元素。