D11. 枚举、模拟与算法复杂度

1.1 算法基础：模拟与枚举思想

目标：理解模拟与枚举的核心思想，掌握其应用场景。

1.1.1 ⭐ 模拟算法：逐步骤复现现实问题

模拟是通过程序逐步骤复现现实问题的流程，例如模拟银行排队、交通信号灯控制等。 核心步骤：

1. 确定问题的输入与输出。
2. 按逻辑顺序分步骤实现每一步操作。

示例：模拟一个简单的“猜数字游戏”

import random
target = random.randint(1, 100)
guess = int(input("猜一个1~100的数字："))
while guess != target:
    if guess < target:
        print("太小！")
    else:
        print("太大！")
    guess = int(input("再猜一次："))
print("恭喜猜中！")

应用场景：

• 需要精确复现流程的问题（如游戏规则、物理模拟）。
• 注意事项：
  • 确保每一步逻辑清晰，避免遗漏边界条件。
  • 复杂问题可能需结合其他算法（如枚举）。

1.1.2 ⭐ 枚举算法：穷举所有可能解

枚举通过列举所有可能的解，并逐一验证是否符合条件。适用于解空间较小的问题。

示例：找出所有各位数字之和为7的三位数

for num in range(100, 1000):
    a, b, c = map(int, str(num))
    if a + b + c == 7:
        print(num)

核心特点：

• 优点：逻辑简单，正确性易验证。
• 缺点：时间复杂度高（如三位数问题需枚举900次）。
• 优化方向：减少枚举范围（如直接枚举a和b，推导c的值）。

1.2 算法的资源消耗：时间和空间

目标：理解算法对时间和内存的需求差异。

1.2.1 时间资源：算法运行速度

算法执行时间由基本运算次数决定，例如：

• 枚举三位数：需900次循环（O(1000)）。
• 双重循环：时间随数据量平方增长（如O(n²)）。

示例对比：

算法类型	问题规模n	运行时间（近似）
线性枚举（O(n))	1000	1秒
双重循环（O(n²))	1000	100万次运算（可能超时）

关键点：

• 大数据量下，时间复杂度高（如指数级）的算法可能无法运行。

1.2.2 空间资源：算法内存占用

算法占用的内存由变量、数据结构等决定。例如：

• 数组a[n]的空间复杂度为O(n)。
• 哈希表可能占用额外空间（如O(n)）。

示例：

# 空间复杂度O(1)
def find_min(arr):
    min_val = arr[0]
    for num in arr:
        if num < min_val:
            min_val = num
    return min_val

# 空间复杂度O(n)
def reverse_array(arr):
    return arr[::-1]

1.3 算法复杂度分析：大O表示法

目标：掌握用大O表示法分析算法复杂度的方法。

1.3.1 渐进分析：关注主导项

大O表示法忽略常数和低阶项，仅保留最高阶项。例如：

• T(n) = 3n² + 5n + 10 → O(n²)
• T(n) = 1000logn + 500 → O(logn)

为什么关注主导项？

• 当输入规模n趋近无穷大时，低阶项的影响可忽略。
• 例如：当n=1000时，n²的值是n的1000倍。

1.3.2 复杂度分类与意义

复杂度	示例算法	可接受规模（n）
O(1)	直接访问数组元素	任意规模
O(logn)	二分查找	亿级数据
O(n)	线性搜索	百万级数据
O(nlogn)	快速排序	十万级数据
O(n²)	双重循环枚举	千级数据
O(2ⁿ)	暴力解旅行商问题	n≤20

1.4 时间复杂度与空间复杂度的计算

目标：学会计算常见算法的时间与空间复杂度。

1.4.1 时间复杂度计算步骤

1. 确定基本操作：如循环内的比较、赋值等。
2. 分析循环结构：
   • 单层循环：O(n)。
   • 双重循环：O(n²)。
   • 递归：需分析递归深度或分治次数。
3. 合并复杂度：取主导项。

示例1：双重循环枚举

for i in range(n):
    for j in range(n):
        print(i + j)  # O(1)
# 时间复杂度：O(n²)

示例2：递归计算斐波那契数

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
# 时间复杂度：O(2ⁿ)（指数级，因重复计算）

1.4.2 空间复杂度计算示例

算法	空间复杂度	原因
线性搜索	O(1)	仅需存储变量
快速排序（递归）	O(logn)	递归栈深度为logn
动态规划（二维表）	O(n²)	需存储二维数组

知识回顾

1. 模拟：按步骤复现问题流程，需逻辑清晰。
2. 枚举：穷举所有可能解，适合小规模问题，需优化减少枚举范围。
3. 复杂度分析：
   • 时间复杂度：用大O表示法描述，关注最高阶项。
   • 空间复杂度：分析算法占用的额外内存。
4. 常见复杂度等级：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)。

课后练习

1. 选择题：以下哪种算法的时间复杂度最低？

   • A. 遍历数组找最大值（O(n)）
   • B. 双重循环求所有数对之和（O(n²)）
   • C. 递归计算阶乘（O(n)）

2. 填空题：计算以下代码的时间复杂度：

   def example(n):
       for i in range(n):
           for j in range(i):
               print("Hello")

   答案：______

3. 代码优化：将三位数枚举的代码优化为减少循环次数。 原代码：

   for a in range(1, 10):
       for b in range(0, 10):
           for c in range(0, 10):
               if a + b + c ==7:
                   print(a*100 + b*10 + c)

   优化方向：仅枚举a和b，计算c的值。

扩展阅读

• 优化技巧：
  • 剪枝：提前终止无效枚举（如枚举到某条件不满足时直接跳出循环）。
  • 数学推导：减少枚举变量数量（如通过公式推导部分值）。
• 工具推荐：使用在线复杂度分析工具（如Big-O Cheat Sheet）辅助理解。