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

不止于python

发布于 2025-03-19 19:32:29

57100

代码可运行

文章被收录于专栏：不止于python不止于python

运行总次数：0

代码可运行

📂 开始上课

还在被时间复杂度、空间复杂度搞得头晕？本篇文章用最简单的语言和丰富的 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²)	双重嵌套循环	创建二维数组	适用于少量数据，但大数据时需优化