第 1 课：时间复杂度与空间复杂度

学习目标

通过本节课的学习，你将能够：

理解为什么需要使用复杂度分析来评估算法的好坏。
掌握大O表示法的基本含义，它表示算法的性能随输入规模增长的趋势。
学会对简单算法的时间复杂度进行分析和估算。
初步认识 空间复杂度的概念。
了解常见的几种复杂度阶数及其在性能上的巨大差异。

核心概念

想象一下，你要从一本1000页的字典里找到一个单词“algorithm”。有两种方法：

方法A：从第一页开始，一页一页地翻，直到找到。运气好的话很快，但运气不好（单词在最后）可能要翻1000次。
方法B：先翻到字典中间，看这个单词在中间的前面还是后面，然后把搜索范围缩小一半。如此重复，很快就能找到。

当字典只有1000页时，两种方法可能都很快。但如果字典有100万页，方法A（最坏情况）可能要翻100万次，而方法B大约只需要20次（2^20 ≈ 100万）。 复杂度分析就是用来量化描述这种性能差异的数学工具，它关注的是随着数据规模(n)变大，算法所需资源（主要是时间和空间）增长的趋势。

1. 大O表示法

大O表示法（Big O Notation）是描述复杂度的标准方式。它不关注算法运行的具体时间（比如0.5秒），而是关注当输入数据规模n变得非常大时，算法执行步骤（时间）或内存使用（空间）的增长量级。

通俗理解：大O表示法就像是给算法的性能表现“贴标签”，比如 O(1)、O(n)、O(n²)。这个标签告诉你，当n变大时，这个算法的性能会如何“恶化”。

2. 时间复杂度

时间复杂度衡量的是算法执行所花费时间的增长趋势。我们通常通过计算算法中基本操作执行的次数来估算它。

常数时间 O(1)：操作次数是固定的，与数据规模n无关。例如，访问数组的第一个元素。
线性时间 O(n)：操作次数与n成正比。例如，遍历一个数组。
平方时间 O(n²)：操作次数与n的平方成正比。例如，嵌套循环遍历一个二维数组。
对数时间 O(log n)：操作次数与n的对数成正比，增长非常缓慢。例如，二分查找。

分析技巧：

关注循环，尤其是嵌套循环。
顺序执行的代码，复杂度取最大值（加法法则）。
嵌套的代码，复杂度相乘（乘法法则）。

3. 空间复杂度

空间复杂度衡量的是算法所需内存空间的增长趋势。它与算法中创建的变量、数据结构等直接相关。

O(1)：使用固定数量的变量，与n无关。
O(n)：需要创建一个大小与n相关的数组或列表。
O(n²)：可能需要创建一个n x n的矩阵。

代码示例

以下是几个 Python 代码示例，用于演示不同复杂度的算法。

# 示例1: O(1) - 常数时间
def get_first_element(arr):
    """返回数组的第一个元素，无论数组多大，操作次数都是1次。"""
    if arr: # 检查数组是否非空
        return arr[0]
    return None

# 示例2: O(n) - 线性时间
def find_max(arr):
    """遍历数组，寻找最大值。需要访问n个元素。"""
    if not arr:
        return None
    max_val = arr[0]
    for num in arr: # 循环次数与数组长度 n 成正比
        if num > max_val:
            max_val = num
    return max_val

# 示例3: O(n²) - 平方时间
def print_pairs(arr):
    """打印数组中所有可能的元素对。"""
    n = len(arr)
    for i in range(n):       # 外层循环 n 次
        for j in range(n):   # 内层循环 n 次
            print(f"({arr[i]}, {arr[j]})")

# 示例4: O(log n) - 对数时间（二分查找）
def binary_search(sorted_arr, target):
    """在一个**已排序**的数组中查找目标值。"""
    low, high = 0, len(sorted_arr) - 1
    while low <= high:       # 每次循环，搜索范围减半
        mid = (low + high) // 2
        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 示例5: 空间复杂度 O(n)
def create_list_of_zeros(n):
    """创建一个包含n个0的列表，空间占用与n成正比。"""
    return [0] * n

# 测试
data = [4, 2, 9, 7, 5]
print("第一个元素:", get_first_element(data)) # O(1)
print("最大值:", find_max(data))             # O(n)
print("\n所有元素对:")
print_pairs([1, 2])                           # O(n²)，当n=2时打印4对
print("\n二分查找(在[1,2,3,4,5]中查找4):")
print(binary_search([1,2,3,4,5], 4))          # O(log n)
print("创建5个零的列表:", create_list_of_zeros(5)) # 空间O(n)

实践练习

练习1（基础） 分析以下两个函数的时间复杂度。

def sum_array(arr):
    total = 0
    for i in arr:
        total += i
    return total

def double_sum(arr):
    total = 0
    for i in arr:
        for j in arr:
            total += i + j
    return total

要求：分别给出每个函数的时间复杂度（使用大O表示法），并简要说明理由。
预期输出： sum_array 的时间复杂度是 O(n)。 double_sum 的时间复杂度是 O(n²)。

练习2（进阶） 下面代码的时间复杂度是多少？

def mystery_function(n):
    i = 1
    while i < n:
        i = i * 2
    return i

要求：分析变量 i 的变化过程，计算 while 循环执行的次数与 n 的关系。
提示：i 的值依次是 1, 2, 4, 8, 16, ...，这是一个等比数列。
预期输出：时间复杂度是 O(log n)。

练习3（综合思考） 请尝试为 “实践练习1” 中的 double_sum 函数写一个空间复杂度为 O(1) 的版本。

要求：函数功能不变（返回所有元素两两之和的总和），但只能使用固定几个变量。

预期输出：函数体大致如下：

def double_sum_v2(arr):
    n = len(arr)
    total = 0
    for i in arr:
        total += i * n # 每个元素 i 会与 n 个元素（包括自己）相加
    return total

常见错误

忽略嵌套循环：只看一个循环的O(n)，而忽略了内部还有循环，导致实际复杂度可能是O(n²)或更高。
混淆最坏情况与平均情况：大O通常描述的是最坏情况下的复杂度。例如，快速排序的平均复杂度是O(n log n)，但最坏情况是O(n²)。
忽视空间复杂度：初学者往往只关注速度（时间复杂度），而忽略了内存消耗（空间复杂度），导致在内存受限的环境下程序无法运行。
过度优化：在没必要（如数据量很小）或优化方向错误（比如将O(n)优化成O(1)但逻辑变得极其复杂）的情况下过度追求低复杂度。

小结

复杂度分析是衡量算法可扩展性的核心工具，它告诉你当数据量变大时，算法性能会如何变化。
大O表示法 (O(1), O(n), O(n²), O(log n)) 描述了算法性能的增长趋势，是评价算法好坏的关键标准之一。
时间复杂度关注执行步骤的增长，通常通过分析循环结构来估算。
空间复杂度关注内存使用的增长。
不要只看具体数字，要思考“如果n变成100万，我的程序会怎样？”
本节课建立的概念是后续学习所有数据结构（如数组、链表、树） 和算法（如排序、搜索） 的理论基石。理解了它们的复杂度，你才能在实际问题中做出正确的技术选型。

下一课预告：我们将从最基本的“数组”数据结构开始，看看它的特性、操作以及这些操作的时间复杂度。

练习编辑器

rust