再谈编程

Python之禅 (The Zen of Python)

在 Python 解释器中输入 import this ，你会看到一段由 Tim Peters 撰写的编程哲学。

它不是语法规则，而是 Python 社区二十多年来沉淀下来的设计智慧。

# 在 Python 交互式环境中
>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
...

核心精神： 优雅、明确、简单 。好的代码应该像散文一样可读。

Python之禅 · 核心要义

Python之禅 · 更多智慧

什么是时间复杂度？

时间复杂度描述的是 算法执行时间随输入规模增长的变化趋势 ，用大 O 记号（Big-O Notation）表示。

我们不关心常数系数和低阶项，只看增长最快的项：

• 不关心具体执行了多少秒（受硬件、语言影响）
• 关心当 n → ∞ 时，操作次数的增长量级
• 最坏情况分析：假设输入总是让算法表现最差

# 例子：计算 1 + 2 + ... + n

# 方法A：循环累加 —— O(n)
def sum_loop(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

# 方法B：公式计算 —— O(1)
def sum_formula(n):
    return n * (n + 1) // 2

# n = 10^9 时，方法A需要循环10亿次，方法B只需1次乘法

常见时间复杂度速查表

经验法则： 在编程竞赛和面试中，O(n log n) 通常是可接受的上限，O(n²) 对于 n > 10⁴ 就要警惕了。

空间复杂度

空间复杂度描述算法执行过程中 额外占用内存随输入规模的增长趋势 。

# O(1) 空间 —— 只使用固定数量的变量
def reverse_array_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# O(n) 空间 —— 创建了新数组
def reverse_array_new(arr):
    result = []           # 额外分配了 n 个空间
    for i in range(len(arr) - 1, -1, -1):
        result.append(arr[i])
    return result

# O(n) 空间 —— 递归调用栈
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # 递归深度为 n

时间复杂度分析实战

分析代码复杂度的三个步骤：

1. 找到最内层循环的操作（基本操作）
2. 计算该操作执行的总次数
3. 保留最高阶项，忽略常数系数

# 例1：嵌套循环 —— O(n²)
for i in range(n):        # n 次
    for j in range(n):    # n 次
        print(i, j)         # 共 n × n = n² 次

# 例2：嵌套但内层受限 —— O(n log n)
for i in range(n):        # n 次
    j = 1
    while j < n:          # log n 次（j 每次翻倍）
        j *= 2
        print(i, j)         # 共 n × log n 次

# 例3：顺序执行 —— 取最大值
for i in range(n):        # O(n)
    print(i)
for j in range(n):        # O(n)
    for k in range(n):    # O(n²)
        print(j, k)
# 总复杂度 = O(n) + O(n²) = O(n²)

经典算法：最大盛水容器

题目描述

给定 n 个非负整数表示容器高度，每根线宽度为 1。找出两根线，使它们与 x 轴围成的容器能盛最多水。

# 输入: height = [1,8,6,2,5,4,8,3,7]
#       索引:  0 1 2 3 4 5 6 7 8
#
#       8 |       █       █
#       7 |       █       █       █
#       6 |       █   █   █       █
#       5 |       █   █   █   █   █
#       4 |       █   █   █   █   █ █
#       3 |       █   █   █   █ █ █ █
#       2 |       █ █ █   █   █ █ █ █
#       1 | █ █ █ █ █ █ █ █ █ █ █ █ █
#       0 +---------------------------
#
# 选择索引1(高8)和索引8(高7)，宽度7，高度取min(8,7)=7
# 面积 = 7 × 7 = 49（最大值）

解法一：暴力枚举

枚举所有可能的左右边界组合，计算面积取最大值。

def max_area_brute(height):
    n = len(height)
    max_area = 0
    
    # 枚举所有 i < j 的组合
    for i in range(n):
        for j in range(i + 1, n):
            # 宽度 = j - i，高度 = 两根线中较矮的那根
            width = j - i
            h = min(height[i], height[j])
            area = width * h
            max_area = max(max_area, area)
    
    return max_area

# 时间复杂度: O(n²) —— 双重循环
# 空间复杂度: O(1)

# 测试
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area_brute(height))  # 输出: 49

当 n = 10⁵ 时，O(n²) 需要 10¹⁰ 次运算， 严重超时 。需要更聪明的解法。

解法二：双指针法 (最优解)

核心思想

初始化左右指针在两端。每次移动 较短的那根线 ，因为移动较长的线不可能获得更大的面积。

def max_area_two_pointer(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # 计算当前面积
        width = right - left
        h = min(height[left], height[right])
        max_area = max(max_area, width * h)
        
        # 移动较短的线（关键！）
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

# 时间复杂度: O(n) —— 只遍历一次
# 空间复杂度: O(1) —— 只用两个指针

双指针法的正确性证明

为什么移动较短的线不会错过最优解？

• 当前面积 = width × min(left_height, right_height)
• 如果移动 较高的线 ：宽度变小了，高度最多不变（仍受限于较矮的线），面积 必然减小
• 如果移动 较矮的线 ：宽度变小，但新线可能更高，面积 有可能增大

# 直观理解（以 height=[1,8,6,2,5,4,8,3,7] 为例）
# 初始: left=0(h=1), right=8(h=7), area=8*1=8
# 移动 left (因为 1 < 7): left=1(h=8), right=8(h=7), area=7*7=49 ← 最优!
# 移动 right (因为 7 < 8): left=1(h=8), right=7(h=3), area=6*3=18
# 移动 right (因为 3 < 8): left=1(h=8), right=6(h=8), area=5*8=40
# ... 直到 left >= right

精髓： 每次移动都"放弃"了当前状态下所有不可能的解，逐步缩小搜索空间。这是贪心算法的典型应用。

重难点回顾