程序员的数学（十一）算法优化中的数学思维：从暴力到高效的蜕变

举报
倔强的石头_ 发表于 2025/12/17 15:44:39 2025/12/17
【摘要】 今天，我们聚焦程序员最核心的需求之一 ——算法优化，通过四个经典算法案例（两数之和、冒泡排序、最长递增子序列、汉诺塔），展示如何用前面学过的数学知识（余数、逻辑、递归、指数爆炸、二分法）驯服 “暴力算法”，将时间复杂度从 O (2ⁿ) 或 O (n²) 降到 O (n log n) 甚至 O (n)。

image.png

@[toc]
欢迎回到 “程序员的数学” 系列第十一篇。前面的内容从基础数学工具（0、逻辑、余数）到综合实战（用户行为分析工具），逐步构建了数学思维体系。今天，我们聚焦程序员最核心的需求之一 ——算法优化，通过四个经典算法案例（两数之和、冒泡排序、最长递增子序列、汉诺塔），展示如何用前面学过的数学知识（余数、逻辑、递归、指数爆炸、二分法）驯服 “暴力算法”，将时间复杂度从 O (2ⁿ) 或 O (n²) 降到 O (n log n) 甚至 O (n)。

算法优化的本质不是 “炫技”，而是 “用数学思维找到问题的规律，减少不必要的计算”。比如用 “余数分组” 实现哈希查找，用 “二分法” 利用指数爆炸的逆过程，用 “循环不变式” 验证优化的正确性 —— 这些都能在前面的章节中找到源头。

一、为什么算法优化需要数学思维？

先看一个真实场景：某电商 APP 的商品搜索功能，初期用 “暴力遍历” 查找商品，当商品数从 1 万涨到 100 万时，响应时间从 0.1 秒变成 10 秒，用户大量流失。后来用 “二分查找 + 哈希索引” 优化，响应时间稳定在 0.001 秒以内 —— 这就是数学思维的力量：用规律替代蛮力。

暴力算法的问题往往是 “没有利用数学规律”：

  • 暴力查找：没利用 “有序” 或 “分组” 规律，遍历所有元素；
  • 暴力排序：没利用 “局部有序” 规律，重复比较已排好的元素；
  • 暴力递归：没利用 “子问题重叠” 规律，重复计算相同子问题。

而数学思维能帮我们找到这些规律，比如：

  • 分组规律（余数）：将元素按哈希值分组，快速定位目标；
  • 有序规律（二分法）：利用 “有序数组” 的特性，每次范围减半；
  • 子问题规律（递归 + 记忆化）：存储已计算的子问题结果，避免重复计算。

二、案例 1：两数之和 —— 用 “余数分组” 从 O (n²) 到 O (n)

1. 问题描述

给定一个整数数组nums和目标值target，找出数组中 “和为目标值” 的两个整数的索引（假设数组中只有一个解，且元素不重复）。示例：nums = [2,7,11,15]，target = 9，输出[0,1]（2+7=9）。

2. 暴力解法：O (n²) 的 “笨办法”

暴力解法的思路是 “遍历所有两两组合”，用两层循环判断和是否为target：

python

def two_sum_brute(nums, target):
    n = len(nums)
    # 两层循环：遍历所有两两组合（i<j，避免重复）
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # 题目保证有解，此处仅为语法完整

# 测试
print(two_sum_brute([2,7,11,15], 9))  # 输出[0,1]

问题：当nums长度为 100 万时，循环次数约为 5×10¹¹ 次，电脑需要跑几天才能出结果 —— 这是 “指数爆炸” 的雏形（第 7 章），两层循环的复杂度是 O (n²)，数据量大时完全不可用。

3. 数学优化：用 “余数分组” 实现哈希查找（O (n)）

优化思路（关联第 3 章 “余数分组”）

我们需要一个 “快速查找补数” 的方法：对于元素nums[i]，补数是target - nums[i]，如果能在 O (1) 时间内找到补数的索引，就能把复杂度降到 O (n)。这里的关键是哈希表—— 它的本质是 “用余数分组”：

  • 将数组元素作为 “键”，索引作为 “值” 存入哈希表；
  • 哈希表的底层用 “余数” 将键分组（比如key % 数组大小），查找时只需计算补数的哈希值，直接定位到对应分组，无需遍历整个数组。

这和第 3 章 “用余数将无穷问题压缩到有限周期” 的思路一致：哈希表用余数将 “所有可能的整数” 压缩到 “有限的桶（分组）” 中，实现快速查找。

优化代码（哈希表实现）

python

def two_sum_hash(nums, target):
    # 哈希表：key=数组元素，value=元素索引（余数分组的载体）
    num_map = {}
    for i, num in enumerate(nums):
        # 计算补数（目标值 - 当前元素）
        complement = target - num
        # 检查补数是否在哈希表中（O(1)查找，得益于余数分组）
        if complement in num_map:
            return [num_map[complement], i]
        # 将当前元素和索引存入哈希表（完成分组）
        num_map[num] = i
    return []

# 测试
print(two_sum_hash([2,7,11,15], 9))  # 输出[0,1]
print(two_sum_hash([3,2,4], 6))     # 输出[1,2]

复杂度分析：只需遍历一次数组（O (n)），每次哈希查找和插入都是 O (1)，总复杂度 O (n)——100 万数据只需遍历 100 万次，毫秒级出结果。

关联知识点：哈希表的底层实现依赖 “余数分组”（第 3 章），将元素按哈希函数（本质是余数运算）分到不同桶中，避免暴力遍历，这是 “用数学规律减少计算量” 的典型案例。

三、案例 2：冒泡排序 —— 用 “逻辑判断” 从 O (n²) 到 O (n)

1. 问题描述

对一个整数数组进行升序排序，示例：nums = [5,2,9,1,5,6]，排序后输出[1,2,5,5,6,9]。

2. 暴力解法：O (n²) 的 “重复比较”

冒泡排序的暴力实现是 “每次遍历交换相邻逆序元素”，不管数组是否已有序，都遍历 n-1 轮：

python

def bubble_sort_brute(nums):
    n = len(nums)
    # 暴力遍历n-1轮
    for i in range(n-1):
        # 每轮遍历未排序部分
        for j in range(n-1 - i):
            # 交换逆序元素
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

# 测试
print(bubble_sort_brute([5,2,9,1,5,6]))  # 输出[1,2,5,5,6,9]

问题：如果数组已经有序（如[1,2,3,4]），暴力解法仍会遍历 n-1 轮，做无用功 —— 这是 “没利用逻辑判断” 的问题（第 2 章），没有判断 “数组是否已有序”。

3. 数学优化：用 “逻辑判断 + 循环不变式” 优化

优化思路（关联第 2 章 “逻辑”、第 4 章 “循环不变式”）

优化点 1：用 “逻辑标记” 判断是否有序 —— 如果某一轮没有交换元素，说明数组已有序，直接退出（避免无用轮次）；优化点 2：用 “记录最后交换位置” 减少内层循环次数 —— 最后一次交换的位置之后的元素已有序，无需再遍历。

同时，用第 4 章的 “循环不变式” 验证优化的正确性：每轮循环后，数组末尾的 i 个元素已排好序（基底：i=0 时成立；归纳：第 i 轮后，第 n-i 个元素是未排序部分的最大值，加入已排序部分）。

优化代码（高效冒泡排序）

python

def bubble_sort_optimized(nums):
    n = len(nums)
    # 记录最后一次交换的位置（初始为n-1，即最后一个元素）
    last_swap_idx = n - 1
    # 循环不变式：每轮后，末尾的sorted_count个元素已有序
    sorted_count = 0
    while sorted_count < n - 1:
        # 逻辑标记：本轮是否发生交换（初始为False）
        swapped = False
        # 内层循环：只遍历未排序部分（0到last_swap_idx-1）
        current_last_swap = 0
        for j in range(last_swap_idx):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True
                current_last_swap = j  # 更新最后交换位置
        # 优化1：若未交换，说明数组已有序，直接退出
        if not swapped:
            break
        # 优化2：更新最后交换位置，减少下轮遍历范围
        last_swap_idx = current_last_swap
        sorted_count += 1
    return nums

# 测试
print(bubble_sort_optimized([5,2,9,1,5,6]))  # 输出[1,2,5,5,6,9]
print(bubble_sort_optimized([1,2,3,4]))        # 输出[1,2,3,4]（仅1轮遍历）

复杂度分析：

  • 最好情况（已有序）：O (n)（仅遍历 1 轮，无交换）；
  • 最坏情况（逆序）：O (n²)（和暴力一致，但实际交换次数减少）；
  • 平均情况：O (n²)（仍为平方级，但常数项比暴力小）。

关联知识点：用 “逻辑标记（swapped）” 判断有序，用 “循环不变式” 验证排序正确性，避免暴力遍历的无用功 —— 这是 “用逻辑规律优化算法步骤” 的案例。

四、案例 3：最长递增子序列 —— 用 “二分法” 从 O (2ⁿ) 到 O (n log n)

1. 问题描述

找到整数数组中 “最长的严格递增子序列” 的长度（子序列不要求连续），示例：nums = [10,9,2,5,3,7,101,18]，最长递增子序列是[2,3,7,101]，长度为 4。

2. 暴力解法：O (2ⁿ) 的 “指数爆炸”

暴力解法是 “枚举所有子序列，判断是否递增，记录最长长度”—— 数组有 n 个元素，每个元素有 “选” 或 “不选” 两种可能，总共有 2ⁿ个子序列，这是典型的 “指数爆炸”

python

def length_of_lis_brute(nums):
    max_len = 0
    n = len(nums)
    
    # 枚举所有子序列（用二进制表示选/不选：mask的第i位为1表示选nums[i]）
    for mask in range(1, 1 << n):  # 1<<n 是2ⁿ，指数爆炸的根源
        current_subseq = []
        for i in range(n):
            if mask & (1 << i):
                current_subseq.append(nums[i])
        # 判断子序列是否递增
        is_increasing = True
        for j in range(1, len(current_subseq)):
            if current_subseq[j] <= current_subseq[j-1]:
                is_increasing = False
                break
        # 更新最长长度
        if is_increasing and len(current_subseq) > max_len:
            max_len = len(current_subseq)
    return max_len

# 测试（仅适用于小数据，n=10时2¹⁰=1024次，n=20时100万次，n=30时10亿次）
print(length_of_lis_brute([10,9,2,5,3,7]))  # 输出3（[2,5,7]）

问题：当 n=30 时，子序列数是 2³⁰≈10 亿，电脑需要跑几小时；n=40 时是 1 万亿，完全不可行 —— 这是第 7 章讲的 “指数爆炸” 陷阱，暴力解法没利用 “递增子序列的规律”。

3. 数学优化：用 “动态规划 + 二分法” 驯服指数爆炸

优化思路（关联第 6 章 “递归记忆化”、第 7 章 “二分法”）

分两步优化：

  1. 动态规划（O (n²)）：用dp[i]表示 “以 nums [i] 结尾的最长递增子序列长度”，dp[i] = max(dp[j]+1)（j<i 且 nums [j]<nums [i]）—— 这是 “递归的记忆化”（第 6 章），存储子问题结果，避免重复枚举；
  2. 二分法（O (n log n)）：维护一个 “递增序列tails”，tails[k]表示 “长度为 k+1 的递增子序列的最小尾元素”，对每个元素用二分法找到插入位置，更新tails—— 这是利用第 7 章 “二分法的指数级效率”，每次插入是 O (log k)，总复杂度 O (n log n)。

优化代码（二分法实现 O (n log n)）

python

def length_of_lis_optimized(nums):
    tails = []  # tails[k]：长度为k+1的递增子序列的最小尾元素
    for num in nums:
        # 二分法：找到num在tails中的插入位置（维持tails递增）
        left, right = 0, len(tails)
        while left < right:
            mid = left + (right - left) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        # 插入num到tails的left位置
        if left == len(tails):
            tails.append(num)  # num是更大的元素，延长序列
        else:
            tails[left] = num  # 替换为更小的尾元素，为后续元素留空间
    # tails的长度就是最长递增子序列的长度
    return len(tails)

# 测试（n=100万也能快速处理）
print(length_of_lis_optimized([10,9,2,5,3,7,101,18]))  # 输出4
print(length_of_lis_optimized([0]))                      # 输出1

原理解释：tails始终是递增的，比如nums = [2,5,3,7]：

  • 处理 2：tails = [2]（长度 1）；
  • 处理 5：tails = [2,5]（长度 2）；
  • 处理 3：二分找到插入位置 1，替换 5 为 3→tails = [2,3]（长度仍 2，但尾元素更小，后续 7 可延长）；
  • 处理 7：插入位置 2→tails = [2,3,7]（长度 3，即最长子序列长度）。

关联知识点：动态规划利用 “递归记忆化” 避免指数爆炸，二分法利用 “指数爆炸的逆过程”，将复杂度从 O (2ⁿ) 降到 O (n log n)—— 这是 “用数学工具驯服指数爆炸” 的核心案例。

五、案例 4：汉诺塔 —— 用 “余数” 从递归到非递归（避栈溢出）

1. 问题描述

将 n 个圆盘从 A 柱移到 C 柱，中间用 B 柱中转，规则：每次移 1 个圆盘，小圆盘不能放大圆盘

2. 递归解法的问题：栈溢出

递归解法简洁，但 n=1000 时会触发 Python 的 “递归深度限制”（默认约 1000），导致RecursionError—— 这是 “递归陷阱”：递归深度过大时栈溢出。

python

def hanoi_recursive(n, a, b, c):
    if n == 1:
        print(f"{a}→{c}", end=" ")
        return
    hanoi_recursive(n-1, a, c, b)
    print(f"{a}→{c}", end=" ")
    hanoi_recursive(n-1, b, a, c)

# 测试（n=1000时栈溢出）
hanoi_recursive(3, 'A', 'B', 'C')  # 输出A→B A→C B→C

3. 数学优化：用 “余数” 实现非递归（O (2ⁿ)，无栈溢出）

优化思路（关联第 3 章 “余数”、第 4 章 “循环”）

汉诺塔的移动步骤有规律，可用 “余数判断” 实现非递归：

  • 若 n 为偶数：圆盘 1 先移到 B 柱，后续按 “C→A→B→C” 循环目标柱；
  • 若 n 为奇数：圆盘 1 先移到 C 柱，后续按 “B→C→A→B” 循环目标柱；
  • 每次移动后，用 “余数” 判断下一个要移动的圆盘（最小的可移动圆盘）。

这利用了第 3 章 “余数的周期性”：移动步骤的目标柱按固定周期循环，用余数可直接定位目标柱，无需递归调用栈。

优化代码（非递归实现）

python

def hanoi_iterative(n, a, b, c):
    # 初始化柱子：用列表表示，0是最底层（大圆盘），-1是最顶层（小圆盘）
    towers = {a: list(range(n, 0, -1)), b: [], c: []}
    # 确定初始目标柱（n为奇数→C，偶数→B）
    if n % 2 == 1:
        target_order = [b, c, a]  # 循环顺序：B→C→A→B...
    else:
        target_order = [c, b, a]  # 循环顺序：C→B→A→C...
    # 总移动次数：2ⁿ -1（汉诺塔公式）
    total_moves = (1 << n) - 1
    
    for move in range(1, total_moves + 1):
        # 步骤1：移动最小圆盘（1号）到当前目标柱
        min_disc = 1
        # 找到最小圆盘所在的柱子
        source = None
        for tower in [a, b, c]:
            if towers[tower] and towers[tower][-1] == min_disc:
                source = tower
                break
        # 确定当前目标柱（按循环顺序）
        current_target = target_order[(move - 1) % 3]
        # 移动最小圆盘
        disc = towers[source].pop()
        towers[current_target].append(disc)
        print(f"{source}→{current_target}", end=" ")
        
        # 步骤2：若不是最后一步，移动次小圆盘（非1号）
        if move == total_moves:
            break
        # 找到次小圆盘的移动方向（从非最小圆盘的柱子，移到另一根非最小圆盘的柱子）
        # 收集有圆盘的柱子（排除最小圆盘所在的目标柱）
        available = [t for t in [a, b, c] if t != current_target and towers[t]]
        if len(available) < 2:
            continue
        # 确定次小圆盘的源和目标（小圆盘移到大圆盘上）
        t1, t2 = available
        disc1 = towers[t1][-1] if towers[t1] else float('inf')
        disc2 = towers[t2][-1] if towers[t2] else float('inf')
        if disc1 < disc2:
            src, dst = t1, t2
        else:
            src, dst = t2, t1
        # 移动次小圆盘
        disc = towers[src].pop()
        towers[dst].append(disc)
        print(f"{src}→{dst}", end=" ")

# 测试（n=1000也无栈溢出，仅输出前10次移动）
print("\n汉诺塔非递归（n=3）：")
hanoi_iterative(3, 'A', 'B', 'C')  # 输出A→B A→C B→C（和递归一致）

关联知识点：用 “余数判断循环目标柱”，用 “循环替代递归”，避免递归栈溢出 —— 这是 “用数学规律规避递归陷阱” 的案例。

六、算法优化的数学思维框架

通过四个案例，我们可以总结出 “算法优化的数学思维框架”，适用于大多数算法优化场景：

  1. 找规律（数学建模）：将算法问题转化为数学模型（如两数之和→余数分组，汉诺塔→周期循环），关联第 1 章、第 3 章；
  2. 降维度 / 降复杂度：用数学工具减少计算量（如二分法→降为 log n，哈希表→降为 O (1)），关联第 7 章、第 5 章；
  3. 避陷阱（边界验证）：用数学规律规避算法陷阱（如递归栈溢出→用循环，指数爆炸→用动态规划），关联第 6 章、第 8 章；
  4. 验正确性（归纳 / 不变式）：用数学方法验证优化后的算法正确（如循环不变式验证排序，归纳法验证动态规划），关联第 4 章。

七、后续学习方向

如果想进一步深化 “算法优化中的数学思维”，可以：

  1. 图论算法：用 “线性代数（矩阵）” 表示图的邻接关系，用 “最短路径算法（Dijkstra）” 中的优先级队列（堆排序，O (log n)）优化，关联线性代数；
  2. 贪心算法：用 “排序不等式”“哈夫曼编码” 中的数学规律，证明贪心选择的正确性，关联第 5 章排列组合、第 7 章指数爆炸；
  3. 字符串算法：用 “KMP 算法” 中的 “部分匹配表”（前缀函数）减少重复比较，本质是 “用数学规律记录已匹配信息”，关联第 4 章归纳法。

八、小结：数学是算法优化的 “隐形引擎”

今天的四个案例展示了数学思维在算法优化中的核心作用：

  • 余数：帮我们实现哈希分组、周期循环；
  • 逻辑：帮我们判断有序、减少无用计算；
  • 递归与记忆化（第 6 章）帮我们避免重复子问题；
  • 二分法与指数爆炸（第 7 章）帮我们将复杂度从指数级降到对数级；
  • 循环不变式（第 4 章）帮我们验证优化的正确性。

算法优化不是 “凭空想出来的技巧”，而是 “用数学规律找到问题的本质，减少不必要的计算”。当你下次遇到一个暴力算法时，不妨问自己：“这个问题有什么数学规律？能不能用余数、二分法、循环不变式优化？”—— 这就是数学思维给你的 “优化直觉”。

如果你在算法优化中用过类似的数学思维，或者有其他想优化的算法案例，欢迎在评论区分享！

下篇预告：算法优化离不开高效的数据结构。下一篇，我们将探讨数据结构设计中的数学思维，看看如何从基础结构出发，设计出高效存储的设计之道。

【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
开发者 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入