本文通过可视化图表深入讲解五种经典算法设计技术的核心思路和执行流程。

1. 分治法 (Divide and Conquer)

核心思想

将大问题分解为小问题，递归解决小问题，然后合并结果。

分治法流程图

流程图示例

graph LR A --- B B --> C[Happy] B --> D(Sad)

graph TD
    A["大问题 P(n)"] --> B{"是否为基本情况?"}
    B -->|是| C["直接求解"]
    B -->|否| D["分解为子问题"]
    D --> E["P(n/2)"]
    D --> F["P(n/2)"]
    E --> G["递归求解左半部分"]
    F --> H["递归求解右半部分"]
    G --> I["左半部分解"]
    H --> J["右半部分解"]
    I --> K["合并解"]
    J --> K
    K --> L["原问题的解"]
    C --> L

    style A fill:#e1f5fe
    style L fill:#c8e6c9
    style K fill:#fff3e0
    style D fill:#f3e5f5

归并排序可视化

原问题描述：给定一个无序的整数数组，要求将其按照从小到大的顺序重新排列。

输入：[38, 27, 43, 3, 9, 82, 10] 输出：[3, 9, 10, 27, 38, 43, 82]

分治策略：

分解：将数组不断二分，直到每个子数组只有一个元素
解决：单个元素天然有序
合并：将两个有序的子数组合并成一个更大的有序数组

graph TD
    A["[38, 27, 43, 3, 9, 82, 10]"] --> B["分解"]
    B --> C["[38, 27, 43, 3]"]
    B --> D["[9, 82, 10]"]
    
    C --> E["[38, 27]"]
    C --> F["[43, 3]"]
    D --> G["[9, 82]"]
    D --> H["[10]"]
    
    E --> I["[38]"]
    E --> J["[27]"]
    F --> K["[43]"]
    F --> L["[3]"]
    G --> M["[9]"]
    G --> N["[82]"]
    
    I --> O["合并 [27, 38]"]
    J --> O
    K --> P["合并 [3, 43]"]
    L --> P
    M --> Q["合并 [9, 82]"]
    N --> Q
    H --> R["[10]"]
    
    O --> S["合并 [3, 27, 38, 43]"]
    P --> S
    Q --> T["合并 [9, 10, 82]"]
    R --> T
    
    S --> U["最终合并 [3, 9, 10, 27, 38, 43, 82]"]
    T --> U
    
    style A fill:#ffebee
    style U fill:#e8f5e8
    style O fill:#fff3e0
    style P fill:#fff3e0
    style Q fill:#fff3e0
    style S fill:#e3f2fd
    style T fill:#e3f2fd

关键特点：

分解阶段：递归地将数组分成两半
合并阶段：将排序好的子数组合并成更大的有序数组
时间复杂度：O(n log n)，稳定排序

最大子数组问题

原问题描述：给定一个整数数组（可能包含正数、负数和零），找到一个连续的子数组，使得该子数组的和最大。

输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出：最大子数组和为6，对应子数组[4, -1, 2, 1]

分治策略：

分解：将数组从中间分成两半
递归求解：分别求左半部分和右半部分的最大子数组和
合并：求跨越中点的最大子数组和
取最大值：返回三者中的最大值

2. 贪心法 (Greedy Algorithm)

核心思想

在每一步选择中都采取当前状态下最好或最优的选择，期望通过局部最优达到全局最优。

贪心法决策流程

graph TD
    A["开始状态"] --> B["当前可选择的选项"]
    B --> C{"评估所有选项"}
    C --> D["选择当前最优解"]
    D --> E{"是否达到目标?"}
    E -->|否| F["更新状态"]
    E -->|是| G["得到最终解"]
    F --> B
    
    style A fill:#e3f2fd
    style G fill:#c8e6c9
    style D fill:#fff3e0
    style C fill:#f3e5f5

活动选择问题可视化

原问题描述：有n个活动要在同一个会议室举行，每个活动都有开始时间和结束时间。由于会议室同时只能举行一个活动，需要选择最多数量的活动，使得它们在时间上不冲突。

输入活动列表：

活动A: 时间段[1,4]
活动B: 时间段[3,5]
活动C: 时间段[0,6]
活动D: 时间段[5,7]
活动E: 时间段[3,9]
活动F: 时间段[5,9]
活动G: 时间段[6,10]
活动H: 时间段[8,11]

期望输出：选择最多的不冲突活动组合

贪心策略：总是选择结束时间最早的活动，这样为后续活动预留最多时间。

gantt
    title 活动选择问题（贪心策略：按结束时间排序）
    dateFormat X
    axisFormat %s
    
    section 可选活动
    活动A(1,4)     :a1, 1, 4
    活动B(3,5)     :a2, 3, 5
    活动C(0,6)     :a3, 0, 6
    活动D(5,7)     :a4, 5, 7
    活动E(3,9)     :a5, 3, 9
    活动F(5,9)     :a6, 5, 9
    活动G(6,10)    :a7, 6, 10
    活动H(8,11)    :a8, 8, 11
    
    section 贪心选择
    选择A(1,4)     :done, s1, 1, 4
    选择D(5,7)     :done, s2, 5, 7
    选择H(8,11)    :done, s3, 8, 11

贪心策略：总是选择结束时间最早的活动，这样为后续活动留出最多时间。

关键特点：

局部最优：每次选择当前最优选项
无后效性：之前的选择不影响后续选择的最优性
适用条件：问题具有贪心选择性质和最优子结构

3. 动态规划法 (Dynamic Programming)

核心思想

将复杂问题分解为重叠的子问题，通过保存子问题的解来避免重复计算。

动态规划解题步骤

graph TD
    A["确定状态"] --> B["建立状态转移方程"]
    B --> C["确定边界条件"]
    C --> D["选择计算顺序"]
    D --> E{"自顶向下 OR 自底向上?"}
    E -->|备忘录法| F["递归 + 记忆化"]
    E -->|表格法| G["迭代填表"]
    F --> H["得到最优解"]
    G --> H
    
    style A fill:#e3f2fd
    style H fill:#c8e6c9
    style E fill:#f3e5f5
    style C fill:#fff3e0

斐波那契数列DP可视化

原问题描述：计算斐波那契数列的第n项。斐波那契数列定义为：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (当n ≥ 2时)

输入：n = 5 输出：F(5) = 5

问题分析：

使用纯递归会导致大量重复计算
例如计算F(5)时，F(3)会被计算多次
动态规划通过保存中间结果避免重复计算

graph LR
    subgraph "递归树（重复计算）"
        A["fib(5)"] --> B["fib(4)"]
        A --> C["fib(3)"]
        B --> D["fib(3)"]
        B --> E["fib(2)"]
        C --> F["fib(2)"]
        C --> G["fib(1)"]
        D --> H["fib(2)"]
        D --> I["fib(1)"]
        E --> J["fib(1)"]
        E --> K["fib(0)"]
        F --> L["fib(1)"]
        F --> M["fib(0)"]
        H --> N["fib(1)"]
        H --> O["fib(0)"]
    end
    
    subgraph "DP表格（避免重复）"
        P["dp[0]=0"] --> Q["dp[1]=1"]
        Q --> R["dp[2]=1"]
        R --> S["dp[3]=2"]
        S --> T["dp[4]=3"]
        T --> U["dp[5]=5"]
    end
    
    style D fill:#ffcdd2
    style F fill:#ffcdd2
    style H fill:#ffcdd2
    style U fill:#c8e6c9

关键特点：

重叠子问题：同样的子问题被多次求解
最优子结构：问题的最优解包含子问题的最优解
状态转移：dp[i] = dp[i-1] + dp[i-2]
时间复杂度：从指数级O(2^n)优化到线性O(n)

0-1背包问题DP解法

原问题描述：给定一个容量为W的背包和n个物品，每个物品有重量wi和价值vi。要求选择一些物品放入背包，使得总重量不超过背包容量，且总价值最大化。

输入示例：

背包容量：W = 7
物品1：重量=1，价值=1
物品2：重量=3，价值=4
物品3：重量=4，价值=5
物品4：重量=5，价值=7

DP状态定义：dp[i][w] = 前i个物品在容量w下的最大价值

状态转移方程：

dp[i][w] = max(dp[i-1][w],                    // 不取第i个物品
               dp[i-1][w-weight[i]] + value[i]) // 取第i个物品

4. 回溯法 (Backtracking)

核心思想

在搜索过程中，当发现当前选择不能得到有效解时，退回到上一步继续搜索其他可能。

回溯法搜索过程

graph TD
    A["开始搜索"] --> B["做出选择"]
    B --> C{"选择是否有效?"}
    C -->|是| D{"是否达到目标?"}
    C -->|否| E["回溯：撤销选择"]
    D -->|是| F["找到解"]
    D -->|否| G["继续搜索下一层"]
    G --> H{"还有其他选择?"}
    H -->|是| B
    H -->|否| E
    E --> I{"还有其他分支?"}
    I -->|是| J["尝试其他选择"]
    I -->|否| K["无解"]
    J --> B
    
    style A fill:#e3f2fd
    style F fill:#c8e6c9
    style K fill:#ffcdd2
    style E fill:#fff3e0
    style C fill:#f3e5f5

N皇后问题可视化（4皇后）

原问题描述：在n×n的国际象棋棋盘上放置n个皇后，使得它们彼此不能相互攻击。在国际象棋中，皇后可以攻击同一行、同一列以及同一对角线上的任意棋子。

具体问题（4皇后）：

棋盘大小：4×4
皇后数量：4个
约束条件：任意两个皇后不能在同一行、同一列、同一对角线上

期望输出：所有可能的放置方案

回溯策略：

逐行放置皇后
对每一行，尝试每一列
检查是否与已放置的皇后冲突
如果冲突，回溯到上一行重新选择
如果无冲突，继续下一行

graph TD
    A["空棋盘"] --> B["第1行放置皇后"]
    B --> C["位置(0,1)"] 
    C --> D["第2行放置皇后"]
    D --> E["位置(1,3)"]
    E --> F["第3行放置皇后"]
    F --> G["尝试(2,0)"]
    G --> H{"冲突检查"}
    H -->|冲突| I["回溯到第3行"]
    I --> J["尝试(2,2)"]
    J --> K{"冲突检查"}
    K -->|冲突| L["回溯到第2行"]
    L --> M["尝试(1,2)"]
    M --> N["继续搜索..."]
    
    H -->|无冲突| O["第4行放置皇后"]
    O --> P["找到解：(0,1)(1,3)(2,0)(3,2)"]
    
    style A fill:#e3f2fd
    style P fill:#c8e6c9
    style I fill:#fff3e0
    style L fill:#fff3e0
    style H fill:#f3e5f5
    style K fill:#f3e5f5

关键特点：

试探性搜索：尝试所有可能的解
剪枝优化：及时发现无效路径并回退
递归结构：每一步都是相同的决策过程
空间复杂度：O(深度)，时间复杂度通常是指数级

5. 分支界限法 (Branch and Bound)

核心思想

通过系统地搜索解空间，使用界限函数剪枝，优先搜索最有希望的分支。

分支界限法搜索策略

graph TD
    A["根节点"] --> B["计算上界"]
    B --> C{"上界 > 当前最优解?"}
    C -->|否| D["剪枝：放弃此分支"]
    C -->|是| E["分支：生成子节点"]
    E --> F["子节点1"]
    E --> G["子节点2"]
    E --> H["子节点3"]
    
    F --> I["计算上界1"]
    G --> J["计算上界2"]
    H --> K["计算上界3"]
    
    I --> L{"上界1 > 最优解?"}
    J --> M{"上界2 > 最优解?"}
    K --> N{"上界3 > 最优解?"}
    
    L -->|是| O["继续分支"]
    L -->|否| P["剪枝"]
    M -->|是| Q["继续分支"]
    M -->|否| R["剪枝"]
    N -->|是| S["继续分支"]
    N -->|否| T["剪枝"]
    
    O --> U["优先队列：按上界排序"]
    Q --> U
    S --> U
    
    style A fill:#e3f2fd
    style U fill:#c8e6c9
    style D fill:#ffcdd2
    style P fill:#ffcdd2
    style R fill:#ffcdd2
    style T fill:#ffcdd2
    style C fill:#f3e5f5

0-1背包问题分支界限可视化

原问题描述：给定一个容量为W的背包和n个物品，每个物品有重量wi和价值vi。要求选择一些物品放入背包，使得总重量不超过背包容量，且总价值最大化。每个物品要么选择（1），要么不选择（0），不能部分选择。

具体实例：

背包容量：W = 10
物品列表：
- 物品1：重量=2，价值=3，价值密度=1.5
- 物品2：重量=3，价值=4，价值密度=1.33
- 物品3：重量=4，价值=5，价值密度=1.25
- 物品4：重量=5，价值=6，价值密度=1.2

期望输出：选择物品的组合，使得总价值最大

分支界限策略：

按价值密度排序物品
使用优先队列，优先探索上界最高的节点
计算每个节点的上界（部分装入估计）
当节点的上界不超过已知最优解时剪枝

graph TD
    A["根节点<br/>w=0, v=0, bound=22"] --> B["物品1选择"]
    B --> C["取物品1<br/>w=2, v=3, bound=22"]
    B --> D["不取物品1<br/>w=0, v=0, bound=19"]
    
    C --> E["物品2选择"]
    E --> F["取物品2<br/>w=5, v=7, bound=22"]
    E --> G["不取物品2<br/>w=2, v=3, bound=17"]
    
    D --> H["物品2选择"]
    H --> I["取物品2<br/>w=3, v=4, bound=19"]
    H --> J["不取物品2<br/>w=0, v=0, bound=15"]
    
    F --> K["物品3选择"]
    K --> L["取物品3<br/>w=9, v=12, bound=22"]
    K --> M["不取物品3<br/>w=5, v=7, bound=16"]
    
    I --> N["物品3选择"]
    N --> O["取物品3<br/>w=7, v=9, bound=19"]
    N --> P["不取物品3<br/>w=3, v=4, bound=13"]
    
    style L fill:#c8e6c9
    style J fill:#ffcdd2
    style P fill:#ffcdd2
    style A fill:#e3f2fd

关键特点：

界限函数：估算子问题可能达到的最优值
优先搜索：优先探索上界最高的节点
剪枝策略：当上界低于已知最优解时剪枝
适用场景：最优化问题，特别是整数规划

算法设计技术对比总结

设计技术	核心思想	适用问题	时间复杂度特点	典型应用
分治法	分解+合并	可分解的问题	通常O(n log n)	排序、查找
贪心法	局部最优	具有贪心选择性质	通常O(n)或O(n log n)	调度、图算法
动态规划	记忆化搜索	重叠子问题+最优子结构	O(状态数×转移)	背包、路径
回溯法	试探+回退	约束满足问题	指数级（有剪枝）	组合、排列
分支界限	搜索+剪枝	最优化问题	指数级（有界限）	整数规划

选择策略

分治法：问题可以自然分解且子问题相互独立
贪心法：每步都能做出最优选择且不影响后续
动态规划：存在重叠子问题，需要最优解
回溯法：需要搜索所有可能解或验证可行性
分支界限法：需要找到最优解且有好的界限估计

完整源码

如果您想查看本文所有排序算法的完整C++实现代码，请点击下方链接：

查看完整C++源码

相关代码实现: 算法设计技术完整C++代码

数据结构——算法设计方法

用动态图表理解五大算法设计方法

1. 分治法 (Divide and Conquer)

核心思想

分治法流程图

流程图示例

归并排序可视化

最大子数组问题

2. 贪心法 (Greedy Algorithm)

核心思想

贪心法决策流程

活动选择问题可视化

3. 动态规划法 (Dynamic Programming)

核心思想

动态规划解题步骤

斐波那契数列DP可视化

0-1背包问题DP解法

4. 回溯法 (Backtracking)

核心思想

回溯法搜索过程

N皇后问题可视化（4皇后）

5. 分支界限法 (Branch and Bound)

核心思想

分支界限法搜索策略

0-1背包问题分支界限可视化

算法设计技术对比总结

选择策略

完整源码

CATALOG

FEATURED TAGS

FRIENDS