超简单！一看就懂的时间复杂度 & 空间复杂度详解（超多 Python 示例） - 不止于python

📂 开始上课

还在被时间复杂度、空间复杂度搞得头晕？本篇文章用最简单的语言和丰富的 Python 示例，带你轻松掌握这些算法基础概念！无论你是算法新手还是想优化代码，这篇文章都能帮你快速理解，让你的代码又快又省！🚀

💡 什么是时间复杂度和空间复杂度？

⏳ 时间复杂度（Time Complexity）

时间复杂度是衡量算法运行时间随输入规模变化的增长速度。它通常用 大 O 符号（O 记号） 表示，比如：

O(1)：运行时间与输入大小无关（最快）
O(n)：运行时间随输入成正比增加
O(n²)：输入翻倍，运行时间变成 4 倍（较慢）

📈 Python 代码示例：时间复杂度解析

1️⃣ O(1) - 常数时间

无论输入大小如何，执行的操作数始终是固定的。

def get_first_element(lst):  
    return lst[0]  # 只执行一次操作  
  
print(get_first_element([1, 2, 3, 4, 5]))  # 输出 1

def is_even(n):  
    return n % 2 == 0  # 只有一次计算  
  
print(is_even(10))  # True

def access_dict(d, key):  
    return d[key]  # 直接访问字典，时间复杂度 O(1)  
  
data = {"a": 10, "b": 20, "c": 30}  
print(access_dict(data, "b"))  # 20

✅ 特点：即使数据量增加，运行时间也不会增长。

2️⃣ O(n) - 线性时间

遍历整个列表，每个元素都要访问一次。

def sum_list(lst):  
    total = 0  
    for num in lst:  # 遍历 n 次  
        total += num  
    return total  
  
print(sum_list([1, 2, 3, 4, 5]))  # 15

def contains(lst, target):  
    for num in lst:  
        if num == target:  
            return True  # 可能在最后一个找到  
    return False  
  
print(contains([1, 2, 3, 4, 5], 3))  # True

def copy_list(lst):  
    return [x for x in lst]  # 复制整个列表，时间复杂度 O(n)  
  
print(copy_list([1, 2, 3, 4, 5]))

✅ 特点：数据量翻倍，执行的次数也翻倍。

3️⃣ O(n²) - 二次方时间

嵌套循环，每个元素都要与所有其他元素比较一次。

def print_pairs(lst):  
    for i in lst:  
        for j in lst:  
            print(i, j)  # 每个 i 都和每个 j 配对  
  
print_pairs([1, 2, 3])

def bubble_sort(arr):  
    n = len(arr)  
    for i in range(n):  
        for j in range(0, n-i-1):  # 经典 O(n²) 排序算法  
            if arr[j] > arr[j+1]:  
                arr[j], arr[j+1] = arr[j+1], arr[j]  
  
arr = [5, 3, 1, 4, 2]  
bubble_sort(arr)  
print(arr)  # [1, 2, 3, 4, 5]

def find_duplicates(lst):  
    duplicates = []  
    for i in range(len(lst)):  
        for j in range(i+1, len(lst)):  # 双重循环  
            if lst[i] == lst[j]:  
                duplicates.append(lst[i])  
    return duplicates  
  
print(find_duplicates([1, 2, 3, 2, 4, 5, 1]))  # [1, 2]

✅ 特点：数据量翻倍，执行的次数变成 4 倍。

📈 Python 代码示例：空间复杂度解析

1️⃣ O(1) - 常数空间

使用固定数量的额外存储空间。

def sum_list(lst):  
    total = 0  # 只使用一个变量  
    for num in lst:  
        total += num  
    return total

def swap(a, b):  
    a, b = b, a  # 只用了 2 个变量  
    return a, b  
  
print(swap(3, 5))  # (5, 3)

✅ 特点：不管数据多大，占用的额外空间都是固定的。

🎯 总结

复杂度	时间示例	空间示例	适用情况
O(1)	直接访问数组元素	只使用几个变量	超快，适用于查找等操作
O(n)	遍历列表	复制列表	适用于大多数线性操作
O(n²)	双重嵌套循环	创建二维数组	适用于少量数据，但大数据时需优化