差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 数据结构:绪论 [2025/12/11 15:32] – [5. 动态规划 (Dynamic Programming)] 张叶安
+++ 数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安
@@ 行 1: / 行 1: @@
-====== 绪论：数据结构与算法详解 ======
+====== 绪论：数据结构与算法详解 (进阶版) ======
-程序设计的核心公式（N.沃思）：
+**"程序设计 = 数据结构 + 算法"** —— 尼克劳斯·沃思 (Niklaus Wirth, 图灵奖得主)
-> **程序 = 数据结构 + 算法**
-  *   **数据结构**：就像是做饭的“食材”和“摆盘方式”（问题的数学模型）。
+如果把编程比作**烹饪**：
-  *   **算法**：就像是“菜谱”和“烹饪步骤”（处理问题的策略）。
+  *   **数据结构 (Data Structure)** 是**食材与厨具的收纳方式**。你是把所有东西堆在桌子上（杂乱无章），还是把蔬菜放保鲜层、肉类放冷冻层、刀具挂在磁吸架上（井井有条）？这决定了你取用材料的效率。
+  *   **算法 (Algorithm)** 是**菜谱与烹饪流程**。是先切菜还是先烧油？是慢火炖还是大火爆炒？这决定了做菜的速度和口味。
+本教程旨在通过可视化的方式，深入剖析计算机科学的这两大基石。
 ===== 第一部分：数据结构 (Data Structure) =====
+数据结构不仅仅是存储数据，更是为了**高效地**检索和操作数据。
 ==== 1. 核心概念辨析 ====
-我们通过一个**“学生信息管理系统”**的例子来理解以下概念：
+在深入具体结构前，我们需要厘清以下术语的层级关系：
-  *   **数据 (Data)**：计算机处理的符号总称。
+^ 术语 ^ 定义 ^ 举例 (学生管理系统) ^
-  *   **数据元素 (Data Element)**：数据的**基本单位**。
+| **数据 (Data)** | 描述客观事物的符号，是计算机操作的对象 | 整个数据库文件 |
-    *   *例子*：学生表中的**一行记录**（包含姓名、学号、班级）。
+| **数据元素 (Data Element)** | 数据的**基本单位**，在程序中通常作为一个整体处理 | 一名学生的完整记录 (行) |
-  *   **数据项 (Data Item)**：构成元素的不可分割的最小单位。
+| **数据项 (Data Item)** | 构成数据元素的**最小单位**，不可分割 | 学生的学号、姓名、性别 (列) |
-    *   *例子*：某条记录中的“**学号**”这一项。
+| **数据对象 (Data Object)** | 性质相同的数据元素的集合 | 所有学生的集合 (表) |
-  *   **数据对象 (Data Object)**：性质相同的数据元素的集合。
-    *   *例子*：**整数集**、**所有学生的集合**。
-==== 2. 逻辑结构：数据之间的“关系” ====
+==== 2. 逻辑结构：数据之间的“思想关系” ====
-逻辑结构描述的是数据在**思想上**的关联，与它们在电脑里存哪里无关。
+逻辑结构是指数据元素之间的相互关系，它与数据在计算机中的存储位置无关。我们通常将其分为四类。
-^ 类型 ^ 关系特点 ^ 生活中的例子 ^ 图示说明 ^
-| **集合结构** | **松散**。除了“同在一个圈子”外，没别的关系。 | 操场上散开做操的同学。 | ( A B C ) |
-| **线性结构** | **一对一**。像一条线，有头有尾，前后相连。 | 排队打饭的队伍；挂在墙上的一串钥匙。 | A -> B -> C |
-| **树状结构** | **一对多**。层次分明，像倒过来的树。 | 电脑里的文件夹（C盘 -> 用户 -> 文档）；家族族谱。 | A -> (B, C) |
-| **图形结构** | **多对多**。错综复杂，四通八达。 | 城市交通网；微信的好友关系网。 | A <-> B <-> C |
-==== 3. 存储结构：数据在“内存”中的样子 ====
-这是逻辑结构在计算机中的**物理实现**。这是本章的重点，我们可以通过 HTML 可视化来理解。
 <html>
-<div style="background-color: #f9f9f9; border: 1px solid #ddd; padding: 15px; border-radius: 5px;">
+<!DOCTYPE html>
-    <h3 style="margin-top:0;">HTML 可视化演示：顺序 vs 链式</h3>
+<html lang="zh-CN">
+<head>
-    <!-- 顺序存储 -->
+<style>
-    <div style="margin-bottom: 20px;">
+    /* 容器基础样式 */
-        <strong>1. 顺序存储 (Sequential Storage) - 类似数组</strong>
+    .ds-container {
-        <p style="font-size:0.9em; color:#666;">特点：物理位置紧邻，像电影院连座。</p>
+        font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, sans-serif;
-        <div style="display: flex;">
+        background-color: #f4f7f6;
-            <div style="border:1px solid #333; width:50px; height:40px; line-height:40px; text-align:center; background:#e0f7fa;">1101</div>
+        padding: 25px;
-            <div style="border:1px solid #333; width:50px; height:40px; line-height:40px; text-align:center; background:#e0f7fa; border-left:none;">1105</div>
+        border-radius: 12px;
-            <div style="border:1px solid #333; width:50px; height:40px; line-height:40px; text-align:center; background:#e0f7fa; border-left:none;">1202</div>
+        border: 1px solid #e0e0e0;
-            <div style="border:1px solid #333; width:50px; height:40px; line-height:40px; text-align:center; background:#e0f7fa; border-left:none;">1203</div>
+        max-width: 900px;
+        margin: 0 auto 20px auto;
+    }
+    .ds-grid {
+        display: grid;
+        grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));
+        gap: 25px;
+    }
+    .ds-card {
+        background: white;
+        padding: 20px;
+        border-radius: 12px;
+        box-shadow: 0 4px 6px rgba(0,0,0,0.05);
+        text-align: center;
+        transition: all 0.3s ease;
+        border-bottom: 3px solid transparent;
+        display: flex;
+        flex-direction: column;
+        align-items: center;
+    }
+    .ds-card:hover {
+        transform: translateY(-7px);
+        box-shadow: 0 10px 20px rgba(0,0,0,0.1);
+        border-bottom-color: #3498db;
+    }
+    .ds-icon-box {
+        height: 110px;
+        width: 100%;
+        display: flex;
+        align-items: center;
+        justify-content: center;
+        margin-bottom: 15px;
+        background: #fafafa;
+        border-radius: 8px;
+    }
+    .ds-svg {
+        width: 140px;
+        height: 90px;
+        overflow: visible;
+    }
+    .ds-shape { fill: #3498db; }
+    .ds-shape-2 { fill: #e74c3c; }
+    .ds-shape-3 { fill: #f1c40f; }
+    .ds-shape-4 { fill: #2ecc71; }
+    .ds-line { stroke: #34495e; stroke-width: 1.5; stroke-linecap: round; }
+    .ds-dashed { stroke: #bdc3c7; stroke-width: 2; stroke-dasharray: 5,3; fill: none; }
+    .anim-float-1 { animation: float 3s infinite ease-in-out; }
+    .anim-float-2 { animation: float 4s infinite ease-in-out 0.5s; }
+    .anim-float-3 { animation: float 3.5s infinite ease-in-out 1.2s; }
+    .anim-float-4 { animation: float 4.5s infinite ease-in-out 2s; }
+    @keyframes float {
+%, 100% { transform: translateY(0); }
+% { transform: translateY(-4px); }
+    }
+    h4 { margin: 0 0 8px 0; color: #2c3e50; font-size: 1.1em; font-weight: 700; }
+    p.desc { font-size: 0.9em; color: #7f8c8d; margin: 0; line-height: 1.5; }
+    p.example { font-size: 0.8em; color: #95a5a6; margin-top: 5px; font-style: italic; }
+</style>
+</head>
+<body>
+<div class="ds-container">
+    <div class="ds-grid">
+        <!-- 1. 集合结构 -->
+        <div class="ds-card">
+            <div class="ds-icon-box">
+                <svg class="ds-svg" viewBox="0 0 140 90">
+                    <ellipse cx="70" cy="45" rx="60" ry="40" class="ds-dashed" />
+                    <circle cx="40" cy="30" r="6" class="ds-shape anim-float-1" />
+                    <circle cx="90" cy="35" r="7" class="ds-shape-2 anim-float-2" />
+                    <circle cx="60" cy="60" r="5" class="ds-shape-3 anim-float-3" />
+                    <circle cx="30" cy="55" r="5" class="ds-shape-4 anim-float-4" />
+                    <circle cx="100" cy="60" r="6" class="ds-shape anim-float-1" />
+                    <circle cx="70" cy="25" r="5" class="ds-shape-3 anim-float-2" />
+                </svg>
+            </div>
+            <h4>集合结构 (Set)</h4>
+            <p class="desc">元素同属一个范围，但无序、无关联。</p>
+            <p class="example">例：购物车里的商品</p>
         </div>
-        <div style="font-size:0.8em; margin-top:5px;">
+        <!-- 2. 线性结构 -->
-            <span style="margin-left:15px;">addr:0</span>
+        <div class="ds-card">
-            <span style="margin-left:20px;">addr:1</span>
+            <div class="ds-icon-box">
-            <span style="margin-left:20px;">addr:2</span>
+                <svg class="ds-svg" viewBox="0 0 140 90">
-            <span style="margin-left:20px;">addr:3</span>
+                    <line x1="20" y1="45" x2="120" y2="45" class="ds-line" />
+                    <circle cx="20" cy="45" r="6" class="ds-shape" />
+                    <circle cx="45" cy="45" r="6" class="ds-shape" />
+                    <circle cx="70" cy="45" r="6" class="ds-shape" />
+                    <circle cx="95" cy="45" r="6" class="ds-shape" />
+                    <circle cx="120" cy="45" r="6" class="ds-shape" />
+                </svg>
+            </div>
+            <h4>线性结构 (Linear)</h4>
+            <p class="desc">元素首尾相接，严格的一对一顺序。</p>
+            <p class="example">例：排队、链表、数组</p>
         </div>
-    </div>
+        <!-- 3. 树状结构 -->
+        <div class="ds-card">
-    <!-- 链式存储 -->
+            <div class="ds-icon-box">
-    <div>
+                <svg class="ds-svg" viewBox="0 0 140 90">
-        <strong>2. 链式存储 (Linked Storage) - 类似寻宝游戏</strong>
+                    <line x1="70" y1="10" x2="40" y2="40" class="ds-line" />
-        <p style="font-size:0.9em; color:#666;">特点：物理位置随意，靠“小纸条(指针)”指引下一站。</p>
+                    <line x1="70" y1="10" x2="100" y2="40" class="ds-line" />
-        <div style="display: flex; align-items: center; flex-wrap: wrap;">
+                    <line x1="40" y1="40" x2="20" y2="75" class="ds-line" />
-            <!-- Node 1 -->
+                    <line x1="40" y1="40" x2="55" y2="75" class="ds-line" />
-            <div style="border:1px solid #333; display:flex; margin-right:5px;">
+                    <line x1="100" y1="40" x2="85" y2="75" class="ds-line" />
-                <div style="padding:10px; background:#fff3e0;">1101</div>
+                    <line x1="100" y1="40" x2="120" y2="75" class="ds-line" />
-                <div style="padding:10px; background:#ffcc80; border-left:1px solid #333;">&bull;</div>
+                    <circle cx="70" cy="10" r="6" class="ds-shape" />
+                    <circle cx="40" cy="40" r="5" class="ds-shape-2" />
+                    <circle cx="100" cy="40" r="5" class="ds-shape-2" />
+                    <circle cx="20" cy="75" r="4" class="ds-shape-4" />
+                    <circle cx="55" cy="75" r="4" class="ds-shape-4" />
+                    <circle cx="85" cy="75" r="4" class="ds-shape-4" />
+                    <circle cx="120" cy="75" r="4" class="ds-shape-4" />
+                </svg>
             </div>
-            <div style="margin-right:5px; font-weight:bold;">&rarr;</div>
+            <h4>树状结构 (Tree)</h4>
+            <p class="desc">一对多的层级关系，严谨的分支体系。</p>
-            <!-- Node 2 -->
+            <p class="example">例：公司组织架构、文件系统</p>
-            <div style="border:1px solid #333; display:flex; margin-right:5px;">
+        </div>
-                <div style="padding:10px; background:#fff3e0;">1105</div>
+        <!-- 4. 图形结构 -->
-                <div style="padding:10px; background:#ffcc80; border-left:1px solid #333;">&bull;</div>
+        <div class="ds-card">
-            </div>
+            <div class="ds-icon-box">
-            <div style="margin-right:5px; font-weight:bold;">&rarr;</div>
+                <svg class="ds-svg" viewBox="0 0 140 90">
+                    <line x1="70" y1="10" x2="20" y2="40" class="ds-line" />
-            <!-- Node 3 -->
+                    <line x1="70" y1="10" x2="120" y2="40" class="ds-line" />
-            <div style="border:1px solid #333; display:flex;">
+                    <line x1="20" y1="40" x2="40" y2="80" class="ds-line" />
-                <div style="padding:10px; background:#fff3e0;">1202</div>
+                    <line x1="120" y1="40" x2="100" y2="80" class="ds-line" />
-                <div style="padding:10px; background:#ffe0b2; border-left:1px solid #333;">^</div>
+                    <line x1="40" y1="80" x2="100" y2="80" class="ds-line" />
+                    <line x1="70" y1="10" x2="40" y2="80" class="ds-line" />
+                    <line x1="70" y1="10" x2="100" y2="80" class="ds-line" />
+                    <line x1="20" y1="40" x2="120" y2="40" class="ds-line" />
+                    <circle cx="70" cy="10" r="6" class="ds-shape" />
+                    <circle cx="20" cy="40" r="6" class="ds-shape-2" />
+                    <circle cx="120" cy="40" r="6" class="ds-shape-2" />
+                    <circle cx="40" cy="80" r="6" class="ds-shape-3" />
+                    <circle cx="100" cy="80" r="6" class="ds-shape-3" />
+                </svg>
             </div>
+            <h4>图形结构 (Graph)</h4>
+            <p class="desc">多对多的网状关系，任意节点皆可相连。</p>
+            <p class="example">例：互联网、神经网络、交通图</p>
         </div>
     </div>
 </div>
+</body>
 </html>
-=== 3.1 详细对比 ===
+=== 2.1 集合 (Set) ===
+  *   **特性**：元素之间除了“同属于一个集合”外，无其他关系。
+  *   **操作**：主要涉及并集、交集、差集、判断元素是否存在。
-| 特性 | 顺序存储 (数组) | 链式存储 (链表) |
+=== 2.2 线性结构 (Linear) ===
-| **物理位置** | 必须相邻。 | 可以不相邻，散落在内存各处。 |
+  *   **特性**：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
-| **关系表示** | 靠位置体现（$A$ 的后面就是 $B$）。 | 靠指针体现（$A$ 手里拿着 $B$ 的地址）。 |
+  *   **典型代表**：
-| **优点** | 查找快（直接算地址），存储密度大。 | 插入、删除快（不用移动元素，改指针即可）。 |
+    *   **数组 (Array)**：连续存储。
-| **缺点** | 插入删除需要移动大量元素；需要预分配空间。 | 查找慢（必须从头找）；指针占用额外空间。 |
+    *   **链表 (Linked List)**：离散存储。
+    *   **栈 (Stack)**：后进先出 (LIFO)，如弹夹。
+    *   **队列 (Queue)**：先进先出 (FIFO)，如排队。
-===== 第二部分：算法 (Algorithm) =====
+=== 2.3 树状结构 (Tree) ===
+  *   **特性**：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。
+  *   **典型代表**：二叉树、红黑树、B树（数据库索引常用）。
-算法不仅要算出结果，还要算得“快”且“省”。
+=== 2.4 图形结构 (Graph) ===
+  *   **特性**：最复杂的结构，节点（顶点）之间可以任意连接（边）。
+  *   **分类**：有向图 vs 无向图；带权图 vs 无权图。
-==== 1. 算法的五大特性 ====
+==== 3. 存储结构：数据在“内存”中的物理形态 ====
-记忆口诀：**有输（出）入，可行确（定）穷**。
-  - **有穷性**：算法不能陷入死循环，必须能跑完。
-  - **确定性**：代码不能模棱两可，同样的输入必须得到同样的输出。
-  - **可行性**：每一步都能通过有限次基本运算完成。
-  - **输入**：0个或多个（例如 `void print_hello()` 就没有输入）。
-  - **输出**：1个或多个（没有输出的算法是无意义的）。
-==== 2. 算法效率度量 ====
+逻辑结构是“想出来的”，存储结构是“写在内存条上的”。
-我们用 **大O记号 ($O$)** 来表示“大概的趋势”，而不是精确的秒数。
+=== 3.1 顺序存储 (Sequential Storage) ===
+  *   **原理**：把逻辑上相邻的元素存储在**物理位置也相邻**的存储单元中。
+  *   **代表**：数组 (Array)。
+  *   **优点**：
+    *   **随机访问**：可以通过下标 $index$ 瞬间找到地址：$Addr = Start + index \times size$。时间复杂度 $O(1)$。
+    *   **存储密度高**：不需要额外空间存指针。
+  *   **缺点**：
+    *   **插入删除困难**：插入一个元素，后面的所有元素都要往后挪，效率低。
+    *   **大小固定**：需要预先分配空间，容易浪费或溢出。
-=== 2.1 时间复杂度 (Time Complexity) ===
+=== 3.2 链式存储 (Linked Storage) ===
-随着数据量 $n$ 的增大，耗时增长的趋势。
+  *   **原理**：逻辑上相邻的元素在物理上可以**不相邻**。通过“指针” (Pointer) 链接。
+  *   **代表**：链表 (Linked List)。
+  *   **优点**：
+    *   **插入删除快**：只需要修改指针指向，不需要移动数据。
+    *   **动态扩展**：有多少数据申请多少内存，不浪费。
+  *   **缺点**：
+    *   **无法随机访问**：想找第10个元素，必须从第1个顺藤摸瓜找下去。时间复杂度 $O(n)$。
+    *   **空间开销**：每个数据都要额外存一个指针地址。
-*   **$O(1)$ 常数阶**：无论数据多少，耗时不变。
+=== 3.3 索引存储与散列存储 ===
-    *   *例子*：访问数组的第 5 个元素 `a[5]`。
+  *   **索引存储 (Index)**：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。
-*   **$O(n)$ 线性阶**：数据翻倍，耗时翻倍。
+  *   **散列存储 (Hash)**：**速度之王**。
-    *   *例子*：遍历一个列表，找某个数。
+    *   不通过比较，而是通过公式（哈希函数）直接计算出存储地址。
-*   **$O(n^2)$ 平方阶**：数据翻倍，耗时变成 4 倍。
+    *   **冲突 (Collision)**：当不同的数据算出了相同的地址时，需要特殊处理（如拉链法）。
-    *   *例子*：双层循环，如冒泡排序。
-*   **$O(\log_2 n)$ 对数阶**：非常快。
-    *   *例子*：二分查找（在有序书中找页码）。
-**效率排序**：
+===== 第二部分：算法 (Algorithm) =====
-$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$
+算法是解决特定问题求解步骤的描述。一个好的算法应该具备：**正确性、可读性、健壮性、高效率**。
+==== 1. 算法效率度量：大O记号 ====
+我们不计算具体的秒数（因为这取决于机器性能），而是计算**操作步骤数量随数据量 $n$ 的增长趋势**。
+<html>
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+    .chart-container {
+        background: white;
+        padding: 20px;
+        border: 1px solid #eee;
+        border-radius: 8px;
+        max-width: 600px;
+        margin: 20px 0;
+    }
+    .bar-chart {
+        display: flex;
+        flex-direction: column;
+        gap: 10px;
+    }
+    .bar-row {
+        display: flex;
+        align-items: center;
+        font-size: 14px;
+    }
+    .bar-label {
+        width: 80px;
+        font-weight: bold;
+        text-align: right;
+        padding-right: 10px;
+    }
+    .bar-track {
+        flex-grow: 1;
+        background: #f0f0f0;
+        height: 20px;
+        border-radius: 10px;
+        overflow: hidden;
+        position: relative;
+    }
+    .bar-fill {
+        height: 100%;
+        display: flex;
+        align-items: center;
+        padding-left: 10px;
+        color: white;
+        font-size: 12px;
+        transition: width 1s ease-out;
+    }
+    .bg-green { background-color: #2ecc71; width: 10%; }
+    .bg-blue { background-color: #3498db; width: 25%; }
+    .bg-orange { background-color: #e67e22; width: 50%; }
+    .bg-red { background-color: #e74c3c; width: 90%; }
+</style>
+</head>
+<body>
+<div class="chart-container">
+    <h4 style="margin-top:0;">时间复杂度直观对比 (n 增大时)</h4>
+    <div class="bar-chart">
+        <div class="bar-row">
+            <div class="bar-label">O(1)</div>
+            <div class="bar-track"><div class="bar-fill bg-green">极快 (索引)</div></div>
+        </div>
+        <div class="bar-row">
+            <div class="bar-label">O(log n)</div>
+            <div class="bar-track"><div class="bar-fill bg-blue">很快 (二分)</div></div>
+        </div>
+        <div class="bar-row">
+            <div class="bar-label">O(n)</div>
+            <div class="bar-track"><div class="bar-fill bg-orange">一般 (遍历)</div></div>
+        </div>
+        <div class="bar-row">
+            <div class="bar-label">O(n²)</div>
+            <div class="bar-track"><div class="bar-fill bg-red">很慢 (冒泡)</div></div>
+        </div>
+    </div>
+</div>
+</body>
+</html>
+=== 1.1 常见复杂度详解 ===
+  *   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。
+<code c>
+    int n = 10000;
+    x = n + 1; // 无论n多大，这行只执行一次
+</code>
+  *   **$O(n)$ 线性阶**：一层循环。
+<code c>
+    for(int i=0; i<n; i++) { ... }
+</code>
+  *   **$O(n^2)$ 平方阶**：双层嵌套循环。
+<code c>
+    for(int i=0; i<n; i++) {
+        for(int j=0; j<n; j++) { ... }
+    }
+</code>
+  *   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。
+<code c>
+    while(n > 1) {
+        n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了
+    }
+</code>
 ===== 第三部分：五大常用算法思想详解 =====
-这是绪论中最具实战意义的部分，以下结合图片内容进行深度解析。
+这是算法的灵魂，掌握这些思想比背诵代码更重要。
 ==== 1. 穷举法 (Brute Force) ====
   *   **别名**：暴力破解法。
-  *   **核心**：**“笨”办法，试遍所有可能**。
+  *   **核心**：列出所有可能的情况，逐一验证。
-  *   **案例**：**破解密码**。
+  *   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
-    *   假设密码是4位数字（0000-9999）。
+  *   **缺点**：效率极低。
-    *   算法：从 0000 开始，一直试到 9999。
+  *   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
-    *   *分析*：理论上一定能找到，但如果密码很长，时间会无法接受。
-==== 2. 递推法与迭代法 ====
+==== 2. 分治法 (Divide and Conquer) ====
-*   **核心**：利用**旧值**推出**新值**。
-*   **案例**：**阶乘计算 ($n!$)**。
-    *   **公式**：$n! = n \times (n-1)!$
-    *   **边界**：$0! = 1$
-    *   **实现**：使用 `for` 循环（迭代）或者函数调用自身（递归）。
-    *   *代码逻辑*：`result = 1; for(i=1; i<=n; i++) { result = result * i; }`
-==== 3. 分治法 (Divide and Conquer) ====
+  *   **核心口诀**：**分而治之，各个击破**。
-  *   **核心**：**大事化小，各个击破**。
+  *   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
-  *   **三步走**：
+  *   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
-    *  **分 (Divide)**：把大问题切成几个**独立的**小问题。
-    *  **治 (Conquer)**：递归解决小问题。
-    *  **合 (Combine)**：把小问题的结果拼起来。
-  *   **案例**：**排序问题**。
-    *   要给 1000 个数排序，先分成两组各 500 个，再分...直到只剩 1 个数（不用排了），然后再两两合并有序序列。
-  *   **关键条件**：子问题必须是**相互独立**的（子问题A的结果不依赖子问题B）。
-==== 4. 贪婪算法 (Greedy Algorithm) ====
+<html>
-  *   **核心**：**目光短浅，只顾眼前**。不追求整体最优，只做当前看起来最好的选择。
+<!DOCTYPE html>
-  *   **特点**：一旦选定，**不回溯**（不后悔）。
+<html>
-  *   **案例**：**找零钱问题**。
+<head>
-    *   *场景*：要找回 15 元，现有面值 11元、5元、1元。
+<style>
-    *   *贪心策略*：优先选最大的。
+    .dc-wrapper {
-        *  选 11元（剩4元）。
+        text-align: center;
-        *  5元不够，选 1元（剩3元）。
+        padding: 15px;
-        *  选 1元...
+        background: #f0f4c3;
-        *  **结果**：1张11元 + 4张1元 = **5张**。
+        border-radius: 8px;
-    *   *问题*：这真的最优吗？
+        border: 1px solid #dce775;
-        *   **最优解其实是**：3张5元 = **3张**。
+    }
-    *   *结论*：贪心算法**快**，但**不一定能得到全局最优解**（除非硬币面值设计得好，如 1, 5, 10）。
+    .dc-block {
+        display: inline-block;
+        background: #8bc34a;
+        color: white;
+        padding: 8px 15px;
+        border-radius: 4px;
+        margin: 5px;
+        font-size: 12px;
+        box-shadow: 0 2px 4px rgba(0,0,0,0.1);
+    }
+    .dc-arrow { color: #555; font-size: 12px; margin: 5px 0; }
+</style>
+</head>
+<body>
+<div class="dc-wrapper">
+    <div class="dc-block" style="width: 200px; background: #33691e;">大问题 (排序 8 个数)</div>
+    <div class="dc-arrow">↓ 拆分 (Divide)</div>
+    <div>
+        <div class="dc-block" style="width: 90px; background: #558b2f;">子问题 A</div>
+        <div class="dc-block" style="width: 90px; background: #558b2f;">子问题 B</div>
+    </div>
+    <div class="dc-arrow">↓ 递归解决 (Conquer)</div>
+    <div>
+        <div class="dc-block">A1</div><div class="dc-block">A2</div>
+        <span style="margin:0 10px; color:#999">|</span>
+        <div class="dc-block">B1</div><div class="dc-block">B2</div>
+    </div>
+    <div class="dc-arrow" style="color: #e65100; font-weight:bold;">↑ 合并结果 (Merge)</div>
+</div>
+</body>
+</html>
+==== 3. 动态规划 (Dynamic Programming, DP) ====
+  *   **核心**：**历史记录**。通过空间换时间。
+  *   **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。
+  *   **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...)
+    *   求第 5 个数：$F(5) = F(4) + F(3)$
+    *   求 $F(4)$ 时需要算 $F(3) + F(2)$。
+    *   **注意**：$F(3)$ 被计算了两次！如果是递归，$n$ 很大时重复计算量是指数级的。
+    *   **DP做法**：算完 $F(3)$ 就把它记在本子上，下次直接看本子。
+<html>
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+    .dp-container {
+        display: flex;
+        gap: 20px;
+        justify-content: center;
+        background: #e3f2fd;
+        padding: 20px;
+        border-radius: 8px;
+        border: 1px solid #bbdefb;
+    }
+    .dp-box {
+        flex: 1;
+        background: white;
+        padding: 10px;
+        border-radius: 6px;
+        text-align: center;
+    }
+    .dp-title { font-weight: bold; color: #1565c0; margin-bottom: 8px; display: block;}
+    .dp-table {
+        display: grid;
+        grid-template-columns: repeat(4, 1fr);
+        gap: 2px;
+        background: #ccc;
+        padding: 2px;
+        margin-top: 10px;
+    }
+    .dp-cell { background: #fff; padding: 5px; font-size: 10px; }
+    .dp-cell.filled { background: #4caf50; color: white; }
+</style>
+</head>
+<body>
+<div class="dp-container">
+    <div class="dp-box">
+        <span class="dp-title">普通递归 (傻算)</span>
+        <div style="font-size: 12px; color: #666;">
+            f(5) 需要算 f(4) 和 f(3)<br>
+            f(4) 需要算 f(3) 和 f(2)<br>
+            <span style="color:red; font-weight:bold;">f(3) 被重复计算了！</span>
+        </div>
+    </div>
+    <div class="dp-box">
+        <span class="dp-title">动态规划 (记账)</span>
+        <div style="font-size: 12px; color: #666;">
+            算过 f(3) 吗？<br>
+            算过 -> <span style="color:green; font-weight:bold;">直接查表</span><br>
+            没算 -> 算出并填表
+        </div>
+        <div class="dp-table">
+            <div class="dp-cell filled">f(1)</div>
+            <div class="dp-cell filled">f(2)</div>
+            <div class="dp-cell filled">f(3)</div>
+            <div class="dp-cell">...</div>
+        </div>
+    </div>
+</div>
+</body>
+</html>
+==== 4. 贪心算法 (Greedy) ====
+  *   **核心**：**活在当下**。
+  *   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。
+  *   **案例：找零钱**
+    *   问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。
+    *   贪心策略：优先用面值最大的。
+    *   步骤：
+        *  66 < 100，跳过。
+        *  66 >= 50，**给一张 50**。剩 16。
+        *  16 < 20，跳过。
+        *  16 >= 10，**给一张 10**。剩 6。
+        *  6 >= 5，**给一张 5**。剩 1。
+        *  **给一张 1**。结束。
+  *   **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。
+==== 5. 回溯法 (Backtracking) ====
+  *   **核心**：**试错与回退**。
+  *   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。
+  *   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。
+  *   **典型应用**：走迷宫、八皇后问题、数独。
+<html>
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+    .bt-maze {
+        position: relative;
+        width: 200px;
+        height: 120px;
+        background: #333;
+        margin: 0 auto;
+        border-radius: 4px;
+        overflow: hidden;
+    }
+    .bt-path {
+        position: absolute;
+        background: #fff;
+        transition: all 0.5s;
+    }
+    .p1 { top: 50px; left: 10px; width: 40px; height: 10px; }
+    .p2 { top: 20px; left: 40px; width: 10px; height: 40px; }
+    .p3 { top: 20px; left: 40px; width: 40px; height: 10px; background: #f44336; }
+    .p4 { top: 50px; left: 40px; width: 60px; height: 10px; }
+    .p5 { top: 50px; left: 90px; width: 10px; height: 40px; }
+    .p6 { top: 80px; left: 90px; width: 60px; height: 10px; background: #4caf50; }
+    .bt-label {
+        position: absolute;
+        color: white;
+        font-size: 10px;
+        padding: 2px;
+    }
+</style>
+</head>
+<body>
+<div style="text-align:center; background:#eee; padding:10px; border-radius:8px;">
+    <div class="bt-maze">
+        <div class="bt-path p1"></div>
+        <div class="bt-path p2"></div>
+        <div class="bt-path p3"></div>
+        <div class="bt-label" style="top:5px; left:50px; color:#ff8a80;">X 死路</div>
+        <div class="bt-path p4"></div>
+        <div class="bt-path p5"></div>
+        <div class="bt-path p6"></div>
+        <div class="bt-label" style="bottom:5px; right:20px; color:#b9f6ca;">√ 通路</div>
+    </div>
+    <p style="font-size:12px; color:#555; margin-top:5px;">先试上方(红)，走不通 -> <strong>回溯</strong> -> 改走右方(绿)</p>
+</div>
+</body>
+</html>
-==== 5. 动态规划 (Dynamic Programming) ====
+===== 总结：如何选择算法？ =====
-  *   **核心**：**精打细算，拒绝重复**。
-  *   **与分治法的区别**：
-    *   分治法处理**独立**子问题。
-    *   动态规划处理**重叠**子问题（即：很多小问题是一样的）。
-  *   **手段**：引入一个**表格（数组）**，算过的结果记下来，下次直接查表，不用重算。
-  *   **案例**：**斐波那契数列 (Fibonacci)**。
-    *   求 `Fib(5)` 需要 `Fib(4)` 和 `Fib(3)`。
-    *   求 `Fib(4)` 需要 `Fib(3)` 和 `Fib(2)`。
-    *   *发现*：`Fib(3)` 被重复计算了！
-    *   *DP做法*：算完 `Fib(3)` 后存入数组 `arr[3]`。下次需要时，直接读取 `arr[3]`。
-  *   **适用场景**：最优化问题，具有**最优子结构**和**重叠子问题**性质。
+| 场景特点 | 推荐策略 | 核心思想 |
+| 问题可拆分，子问题独立 | **分治法** | 大事化小 |
+| 问题可拆分，子问题重叠 | **动态规划** | 拒绝健忘，查表 |
+| 需要快速找到一个可行解 | **贪心算法** | 目光短浅，先拿再说 |
+| 需要遍历所有解或路径 | **回溯法** | 不撞南墙不回头 |
+| 没有任何规律 | **穷举法** | 暴力出奇迹 |

Detach Close

您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。

差别

该主题尚不存在

张叶安的博客