差别

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

--- 数据结构:绪论 [2025/12/11 15:37] – 张叶安
+++ 数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安
@@ 行 1: / 行 1: @@
 ====== 绪论：数据结构与算法详解 (进阶版) ======
-程序设计的核心公式（N.沃思）：
+**"程序设计 = 数据结构 + 算法"** —— 尼克劳斯·沃思 (Niklaus Wirth, 图灵奖得主)
-> **程序 = 数据结构 (骨架) + 算法 (灵魂)**
-  * **数据结构**：是**静态**的。就像图书馆的书架，决定了书怎么放（是按首字母放，还是按类别放）。
+如果把编程比作**烹饪**：
-  * **算法**：是**动态**的。就像图书管理员找书的流程（是从左往右一本本找，还是先查索引再找）。
+  *   **数据结构 (Data Structure)** 是**食材与厨具的收纳方式**。你是把所有东西堆在桌子上（杂乱无章），还是把蔬菜放保鲜层、肉类放冷冻层、刀具挂在磁吸架上（井井有条）？这决定了你取用材料的效率。
+  *   **算法 (Algorithm)** 是**菜谱与烹饪流程**。是先切菜还是先烧油？是慢火炖还是大火爆炒？这决定了做菜的速度和口味。
+本教程旨在通过可视化的方式，深入剖析计算机科学的这两大基石。
 ===== 第一部分：数据结构 (Data Structure) =====
+数据结构不仅仅是存储数据，更是为了**高效地**检索和操作数据。
 ==== 1. 核心概念辨析 ====
-我们通过一个**“学生信息管理系统”**的例子来理解：
+在深入具体结构前，我们需要厘清以下术语的层级关系：
-  * **数据 (Data)**：计算机处理的符号总称。
+^ 术语 ^ 定义 ^ 举例 (学生管理系统) ^
-  * **数据元素 (Data Element)**：数据的**基本单位**（例：学生表中的一行记录）。
+| **数据 (Data)** | 描述客观事物的符号，是计算机操作的对象 | 整个数据库文件 |
-  * **数据项 (Data Item)**：构成元素的最小单位（例：记录中的“学号”）。
+| **数据元素 (Data Element)** | 数据的**基本单位**，在程序中通常作为一个整体处理 | 一名学生的完整记录 (行) |
-  * **数据对象 (Data Object)**：性质相同的数据元素的集合（例：所有学生的集合）。
+| **数据项 (Data Item)** | 构成数据元素的**最小单位**，不可分割 | 学生的学号、姓名、性别 (列) |
+| **数据对象 (Data Object)** | 性质相同的数据元素的集合 | 所有学生的集合 (表) |
-==== 2. 逻辑结构可视化 ====
+==== 2. 逻辑结构：数据之间的“思想关系” ====
-逻辑结构描述的是数据在**思想上**的关联。以下是四种基本结构的交互式演示：
+逻辑结构是指数据元素之间的相互关系，它与数据在计算机中的存储位置无关。我们通常将其分为四类。
 <html>
@@ 行 27: / 行 32: @@
 <head>
 <style>
+    /* 容器基础样式 */
     .ds-container {
-        font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
+        font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, sans-serif;
-        background-color: #f8f9fa;
+        background-color: #f4f7f6;
-        padding: 20px;
+        padding: 25px;
-        border-radius: 8px;
+        border-radius: 12px;
-        border: 1px solid #ddd;
+        border: 1px solid #e0e0e0;
-        margin-bottom: 20px;
+        max-width: 900px;
+        margin: 0 auto 20px auto;
     }
     .ds-grid {
         display: grid;
-        grid-template-columns: repeat(auto-fit, minmax(200px, 1fr));
+        grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));
-        gap: 20px;
+        gap: 25px;
     }
     .ds-card {
         background: white;
-        padding: 15px;
+        padding: 20px;
-        border-radius: 8px;
+        border-radius: 12px;
-        box-shadow: 0 2px 5px rgba(0,0,0,0.1);
+        box-shadow: 0 4px 6px rgba(0,0,0,0.05);
         text-align: center;
-        transition: transform 0.2s;
+        transition: all 0.3s ease;
+        border-bottom: 3px solid transparent;
+        display: flex;
+        flex-direction: column;
+        align-items: center;
     }
     .ds-card:hover {
-        transform: translateY(-5px);
+        transform: translateY(-7px);
-        box-shadow: 0 5px 15px rgba(0,0,0,0.2);
+        box-shadow: 0 10px 20px rgba(0,0,0,0.1);
+        border-bottom-color: #3498db;
     }
-    .ds-icon {
+    .ds-icon-box {
-        height: 80px;
+        height: 110px;
+        width: 100%;
         display: flex;
         align-items: center;
         justify-content: center;
-        margin-bottom: 10px;
+        margin-bottom: 15px;
+        background: #fafafa;
+        border-radius: 8px;
     }
-    .ds-node {
+    .ds-svg {
-        width: 20px;
+        width: 140px;
-        height: 20px;
+        height: 90px;
-        background-color: #3498db;
+        overflow: visible;
-        border-radius: 50%;
+    }
-        display: inline-block;
+    .ds-shape { fill: #3498db; }
-        position: relative;
+    .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; }
-    .set-anim .ds-node { margin: 5px; animation: float 3s infinite ease-in-out; }
+    p.desc { font-size: 0.9em; color: #7f8c8d; margin: 0; line-height: 1.5; }
-    @keyframes float { 0%, 100% { transform: translateY(0); } 50% { transform: translateY(-5px); } }
+    p.example { font-size: 0.8em; color: #95a5a6; margin-top: 5px; font-style: italic; }
-    /* 线性结构 */
-    .linear-box { display: flex; gap: 5px; justify-content: center; align-items: center; }
-    .linear-line { width: 15px; height: 2px; background: #333; }
-    /* 树形结构 */
-    .tree-box { display: flex; flex-direction: column; align-items: center; }
-    .tree-row { display: flex; gap: 20px; margin-top: 5px; }
-    /* 图形结构 */
-    .graph-box { position: relative; width: 80px; height: 60px; margin: 0 auto; }
-    .g-node { position: absolute; }
-    .g-line { position: absolute; background: #333; height: 1px; transform-origin: 0 0; }
-    h4 { margin: 10px 0 5px; color: #2c3e50; }
-    p.desc { font-size: 0.9em; color: #666; margin: 0; }
 </style>
 </head>
@@ 行 91: / 行 101: @@
 <div class="ds-container">
     <div class="ds-grid">
-        <!-- 集合 -->
+        <!-- 1. 集合结构 -->
         <div class="ds-card">
-            <div class="ds-icon set-anim">
+            <div class="ds-icon-box">
-                <div class="ds-node"></div><div class="ds-node" style="background:#e74c3c"></div>
+                <svg class="ds-svg" viewBox="0 0 140 90">
-                <div class="ds-node" style="background:#f1c40f"></div>
+                    <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">松散关系，仅同属一个集合。<br>(例：操场上的同学)</p>
+            <p class="desc">元素同属一个范围，但无序、无关联。</p>
+            <p class="example">例：购物车里的商品</p>
         </div>
-        <!-- 线性 -->
+        <!-- 2. 线性结构 -->
         <div class="ds-card">
-            <div class="ds-icon">
+            <div class="ds-icon-box">
-                <div class="linear-box">
+                <svg class="ds-svg" viewBox="0 0 140 90">
-                    <div class="ds-node"></div><div class="linear-line"></div>
+                    <line x1="20" y1="45" x2="120" y2="45" class="ds-line" />
-                    <div class="ds-node"></div><div class="linear-line"></div>
+                    <circle cx="20" cy="45" r="6" class="ds-shape" />
-                    <div class="ds-node"></div>
+                    <circle cx="45" cy="45" r="6" class="ds-shape" />
-                </div>
+                    <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">一对一，首尾相接。<br>(例：排队)</p>
+            <p class="desc">元素首尾相接，严格的一对一顺序。</p>
+            <p class="example">例：排队、链表、数组</p>
         </div>
-        <!-- 树形 -->
+        <!-- 3. 树状结构 -->
         <div class="ds-card">
-            <div class="ds-icon">
+            <div class="ds-icon-box">
-                <div class="tree-box">
+                <svg class="ds-svg" viewBox="0 0 140 90">
-                    <div class="ds-node"></div>
+                    <line x1="70" y1="10" x2="40" y2="40" class="ds-line" />
-                    <div class="tree-row">
+                    <line x1="70" y1="10" x2="100" y2="40" class="ds-line" />
-                        <div class="ds-node"></div>
+                    <line x1="40" y1="40" x2="20" y2="75" class="ds-line" />
-                        <div class="ds-node"></div>
+                    <line x1="40" y1="40" x2="55" y2="75" class="ds-line" />
-                    </div>
+                    <line x1="100" y1="40" x2="85" y2="75" class="ds-line" />
-                </div>
+                    <line x1="100" y1="40" x2="120" y2="75" class="ds-line" />
+                    <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>
             <h4>树状结构 (Tree)</h4>
-            <p class="desc">一对多，层次分明。<br>(例：文件夹)</p>
+            <p class="desc">一对多的层级关系，严谨的分支体系。</p>
+            <p class="example">例：公司组织架构、文件系统</p>
         </div>
-        <!-- 图形 -->
+        <!-- 4. 图形结构 -->
         <div class="ds-card">
-            <div class="ds-icon">
+            <div class="ds-icon-box">
-                <div class="graph-box">
+                <svg class="ds-svg" viewBox="0 0 140 90">
-                    <div class="ds-node g-node" style="top:0; left:30px;"></div>
+                    <line x1="70" y1="10" x2="20" y2="40" class="ds-line" />
-                    <div class="ds-node g-node" style="bottom:0; left:0;"></div>
+                    <line x1="70" y1="10" x2="120" y2="40" class="ds-line" />
-                    <div class="ds-node g-node" style="bottom:0; right:0;"></div>
+                    <line x1="20" y1="40" x2="40" y2="80" class="ds-line" />
-                    <!-- 简单的连线模拟 -->
+                    <line x1="120" y1="40" x2="100" y2="80" class="ds-line" />
-                    <div style="position:absolute; top:10px; left:40px; width:30px; height:1px; background:#333; transform: rotate(60deg);"></div>
+                    <line x1="40" y1="80" x2="100" y2="80" class="ds-line" />
-                    <div style="position:absolute; top:10px; left:10px; width:30px; height:1px; background:#333; transform: rotate(-60deg);"></div>
+                    <line x1="70" y1="10" x2="40" y2="80" class="ds-line" />
-                    <div style="position:absolute; bottom:10px; left:20px; width:40px; height:1px; background:#333;"></div>
+                    <line x1="70" y1="10" x2="100" y2="80" class="ds-line" />
-                </div>
+                    <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">多对多，错综复杂。<br>(例：交通网)</p>
+            <p class="desc">多对多的网状关系，任意节点皆可相连。</p>
+            <p class="example">例：互联网、神经网络、交通图</p>
         </div>
     </div>
 </div>
 </body>
-</html>
 </html>
-==== 3. 存储结构：数据在“内存”中的样子 ====
+=== 2.1 集合 (Set) ===
+  *   **特性**：元素之间除了“同属于一个集合”外，无其他关系。
+  *   **操作**：主要涉及并集、交集、差集、判断元素是否存在。
-这是逻辑结构的物理实现。
+=== 2.2 线性结构 (Linear) ===
+  *   **特性**：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
+  *   **典型代表**：
+    *   **数组 (Array)**：连续存储。
+    *   **链表 (Linked List)**：离散存储。
+    *   **栈 (Stack)**：后进先出 (LIFO)，如弹夹。
+    *   **队列 (Queue)**：先进先出 (FIFO)，如排队。
-=== 3.1 顺序存储 vs 链式存储 ===
+=== 2.3 树状结构 (Tree) ===
+  *   **特性**：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。
+  *   **典型代表**：二叉树、红黑树、B树（数据库索引常用）。
-^ 特性 ^ 顺序存储 (数组) ^ 链式存储 (链表) ^
+=== 2.4 图形结构 (Graph) ===
-| **物理位置** | 必须相邻 | 可以散落在内存各处 |
+  *   **特性**：最复杂的结构，节点（顶点）之间可以任意连接（边）。
-| **优点** | **查找快** (直接算地址)，存储密度大 | **增删快** (改指针即可)，不需预分配 |
+  *   **分类**：有向图 vs 无向图；带权图 vs 无权图。
-| **缺点** | 插入删除需移动元素 | 查找慢 (必须从头找)，指针占空间 |
-=== 3.2 进阶存储方式 ===
+==== 3. 存储结构：数据在“内存”中的物理形态 ====
-  * **索引存储**：建立一张“目录表”。先查目录找到地址，再找内容。（类似字典的拼音索引）。
+逻辑结构是“想出来的”，存储结构是“写在内存条上的”。
-  * **散列存储 (Hash)**：**速度之王**。
-    * //原理//：通过公式直接算出地址。
+=== 3.1 顺序存储 (Sequential Storage) ===
-    * //例子//：存 `105`，公式 `key % 10`，直接扔进 `5` 号房间。查找时直接去 `5` 号拿。
+  *   **原理**：把逻辑上相邻的元素存储在**物理位置也相邻**的存储单元中。
+  *   **代表**：数组 (Array)。
+  *   **优点**：
+    *   **随机访问**：可以通过下标 $index$ 瞬间找到地址：$Addr = Start + index \times size$。时间复杂度 $O(1)$。
+    *   **存储密度高**：不需要额外空间存指针。
+  *   **缺点**：
+    *   **插入删除困难**：插入一个元素，后面的所有元素都要往后挪，效率低。
+    *   **大小固定**：需要预先分配空间，容易浪费或溢出。
+=== 3.2 链式存储 (Linked Storage) ===
+  *   **原理**：逻辑上相邻的元素在物理上可以**不相邻**。通过“指针” (Pointer) 链接。
+  *   **代表**：链表 (Linked List)。
+  *   **优点**：
+    *   **插入删除快**：只需要修改指针指向，不需要移动数据。
+    *   **动态扩展**：有多少数据申请多少内存，不浪费。
+  *   **缺点**：
+    *   **无法随机访问**：想找第10个元素，必须从第1个顺藤摸瓜找下去。时间复杂度 $O(n)$。
+    *   **空间开销**：每个数据都要额外存一个指针地址。
+=== 3.3 索引存储与散列存储 ===
+  *   **索引存储 (Index)**：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。
+  *   **散列存储 (Hash)**：**速度之王**。
+    *   不通过比较，而是通过公式（哈希函数）直接计算出存储地址。
+    *   **冲突 (Collision)**：当不同的数据算出了相同的地址时，需要特殊处理（如拉链法）。
 ===== 第二部分：算法 (Algorithm) =====
-==== 1. 算法效率度量 (Big O) ====
+算法是解决特定问题求解步骤的描述。一个好的算法应该具备：**正确性、可读性、健壮性、高效率**。
+==== 1. 算法效率度量：大O记号 ====
-我们用 **大O记号** 表示随着数据量 $n$ 增大，耗时增长的趋势。
+我们不计算具体的秒数（因为这取决于机器性能），而是计算**操作步骤数量随数据量 $n$ 的增长趋势**。
 <html>
@@ 行 218: / 行 289: @@
         transition: width 1s ease-out;
     }
-    /* 颜色定义 */
     .bg-green { background-color: #2ecc71; width: 10%; }
     .bg-blue { background-color: #3498db; width: 25%; }
@@ 行 248: / 行 318: @@
 </div>
 </body>
-</html>
 </html>
-  * **$O(1)$ 常数阶**：无论数据多少，耗时不变。
+=== 1.1 常见复杂度详解 ===
-  * **$O(n)$ 线性阶**：数据翻倍，耗时翻倍。
-  * **$O(n^2)$ 平方阶**：数据翻倍，耗时变 4 倍（双层循环）。
+  *   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。
-  * **$O(\log_2 n)$ 对数阶**：非常快（二分查找）。
+<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) ====
-  * **核心**：暴力破解，试遍所有可能。
-  * **优化**：**剪枝 (Pruning)**。如果在搜索过程中发现当前路径不可能成功，就直接放弃，不再往下试（剪掉树枝）。
+  *   **别名**：暴力破解法。
+  *   **核心**：列出所有可能的情况，逐一验证。
+  *   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
+  *   **缺点**：效率极低。
+  *   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
+==== 2. 分治法 (Divide and Conquer) ====
+  *   **核心口诀**：**分而治之，各个击破**。
+  *   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
+  *   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
+<html>
+<!DOCTYPE html>
+<html>
+<head>
+<style>
+    .dc-wrapper {
+        text-align: center;
+        padding: 15px;
+        background: #f0f4c3;
+        border-radius: 8px;
+        border: 1px solid #dce775;
+    }
+    .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>
+===== 总结：如何选择算法？ =====
+| 场景特点 | 推荐策略 | 核心思想 |
+| 问题可拆分，子问题独立 | **分治法** | 大事化小 |
+| 问题可拆分，子问题重叠 | **动态规划** | 拒绝健忘，查表 |
+| 需要快速找到一个可行解 | **贪心算法** | 目光短浅，先拿再说 |
+| 需要遍历所有解或路径 | **回溯法** | 不撞南墙不回头 |
+| 没有任何规律 | **穷举法** | 暴力出奇迹 |

Detach Close

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

差别

该主题尚不存在

张叶安的博客