差别

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

--- 数据结构:绪论 [2025/12/11 16:19] – [绪论：数据结构与算法详解 (进阶版)] 张叶安
+++ 数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安
@@ 行 186: / 行 186: @@
 === 2.1 集合 (Set) ===
-*   **特性**：元素之间除了“同属于一个集合”外，无其他关系。
+  *   **特性**：元素之间除了“同属于一个集合”外，无其他关系。
-*   **操作**：主要涉及并集、交集、差集、判断元素是否存在。
+  *   **操作**：主要涉及并集、交集、差集、判断元素是否存在。
 === 2.2 线性结构 (Linear) ===
-*   **特性**：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
+  *   **特性**：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
-*   **典型代表**：
+  *   **典型代表**：
     *   **数组 (Array)**：连续存储。
     *   **链表 (Linked List)**：离散存储。
@@ 行 198: / 行 198: @@
 === 2.3 树状结构 (Tree) ===
-*   **特性**：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。
+  *   **特性**：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。
-*   **典型代表**：二叉树、红黑树、B树（数据库索引常用）。
+  *   **典型代表**：二叉树、红黑树、B树（数据库索引常用）。
 === 2.4 图形结构 (Graph) ===
-*   **特性**：最复杂的结构，节点（顶点）之间可以任意连接（边）。
+  *   **特性**：最复杂的结构，节点（顶点）之间可以任意连接（边）。
-*   **分类**：有向图 vs 无向图；带权图 vs 无权图。
+  *   **分类**：有向图 vs 无向图；带权图 vs 无权图。
 ==== 3. 存储结构：数据在“内存”中的物理形态 ====
@@ 行 210: / 行 210: @@
 === 3.1 顺序存储 (Sequential Storage) ===
-*   **原理**：把逻辑上相邻的元素存储在**物理位置也相邻**的存储单元中。
+  *   **原理**：把逻辑上相邻的元素存储在**物理位置也相邻**的存储单元中。
-*   **代表**：数组 (Array)。
+  *   **代表**：数组 (Array)。
-*   **优点**：
+  *   **优点**：
     *   **随机访问**：可以通过下标 $index$ 瞬间找到地址：$Addr = Start + index \times size$。时间复杂度 $O(1)$。
     *   **存储密度高**：不需要额外空间存指针。
-*   **缺点**：
+  *   **缺点**：
     *   **插入删除困难**：插入一个元素，后面的所有元素都要往后挪，效率低。
     *   **大小固定**：需要预先分配空间，容易浪费或溢出。
 === 3.2 链式存储 (Linked Storage) ===
-*   **原理**：逻辑上相邻的元素在物理上可以**不相邻**。通过“指针” (Pointer) 链接。
+  *   **原理**：逻辑上相邻的元素在物理上可以**不相邻**。通过“指针” (Pointer) 链接。
-*   **代表**：链表 (Linked List)。
+  *   **代表**：链表 (Linked List)。
-*   **优点**：
+  *   **优点**：
     *   **插入删除快**：只需要修改指针指向，不需要移动数据。
     *   **动态扩展**：有多少数据申请多少内存，不浪费。
-*   **缺点**：
+  *   **缺点**：
     *   **无法随机访问**：想找第10个元素，必须从第1个顺藤摸瓜找下去。时间复杂度 $O(n)$。
     *   **空间开销**：每个数据都要额外存一个指针地址。
 === 3.3 索引存储与散列存储 ===
-*   **索引存储 (Index)**：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。
+  *   **索引存储 (Index)**：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。
-*   **散列存储 (Hash)**：**速度之王**。
+  *   **散列存储 (Hash)**：**速度之王**。
     *   不通过比较，而是通过公式（哈希函数）直接计算出存储地址。
     *   **冲突 (Collision)**：当不同的数据算出了相同的地址时，需要特殊处理（如拉链法）。
@@ 行 322: / 行 322: @@
 === 1.1 常见复杂度详解 ===
-*   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。
+  *   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。
-    <code c>
+<code c>
     int n = 10000;
     x = n + 1; // 无论n多大，这行只执行一次
-    </code>
+</code>
-*   **$O(n)$ 线性阶**：一层循环。
+  *   **$O(n)$ 线性阶**：一层循环。
-    <code c>
+<code c>
     for(int i=0; i<n; i++) { ... }
-    </code>
+</code>
-*   **$O(n^2)$ 平方阶**：双层嵌套循环。
+  *   **$O(n^2)$ 平方阶**：双层嵌套循环。
-    <code c>
+<code c>
     for(int i=0; i<n; i++) {
         for(int j=0; j<n; j++) { ... }
     }
-    </code>
+</code>
-*   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。
+  *   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。
-    <code c>
+<code c>
     while(n > 1) {
         n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了
     }
-    </code>
+</code>
 ===== 第三部分：五大常用算法思想详解 =====
@@ 行 350: / 行 350: @@
 ==== 1. 穷举法 (Brute Force) ====
-*   **别名**：暴力破解法。
+  *   **别名**：暴力破解法。
-*   **核心**：列出所有可能的情况，逐一验证。
+  *   **核心**：列出所有可能的情况，逐一验证。
-*   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
+  *   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
-*   **缺点**：效率极低。
+  *   **缺点**：效率极低。
-*   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
+  *   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
 ==== 2. 分治法 (Divide and Conquer) ====
-*   **核心口诀**：**分而治之，各个击破**。
+  *   **核心口诀**：**分而治之，各个击破**。
-*   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
+  *   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。
-*   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
+  *   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
 <html>
@@ 行 408: / 行 408: @@
 ==== 3. 动态规划 (Dynamic Programming, DP) ====
-*   **核心**：**历史记录**。通过空间换时间。
+  *   **核心**：**历史记录**。通过空间换时间。
-*   **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。
+  *   **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。
-*   **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...)
+  *   **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...)
     *   求第 5 个数：$F(5) = F(4) + F(3)$
     *   求 $F(4)$ 时需要算 $F(3) + F(2)$。
@@ 行 480: / 行 480: @@
 ==== 4. 贪心算法 (Greedy) ====
-*   **核心**：**活在当下**。
+  *   **核心**：**活在当下**。
-*   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。
+  *   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。
-*   **案例：找零钱**
+  *   **案例：找零钱**
     *   问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。
     *   贪心策略：优先用面值最大的。
     *   步骤：
-.  66 < 100，跳过。
+        *  66 < 100，跳过。
-.  66 >= 50，**给一张 50**。剩 16。
+        *  66 >= 50，**给一张 50**。剩 16。
-.  16 < 20，跳过。
+        *  16 < 20，跳过。
-.  16 >= 10，**给一张 10**。剩 6。
+        *  16 >= 10，**给一张 10**。剩 6。
-.  6 >= 5，**给一张 5**。剩 1。
+        *  6 >= 5，**给一张 5**。剩 1。
-.  **给一张 1**。结束。
+        *  **给一张 1**。结束。
-*   **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。
+  *   **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。
 ==== 5. 回溯法 (Backtracking) ====
-*   **核心**：**试错与回退**。
+  *   **核心**：**试错与回退**。
-*   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。
+  *   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。
-*   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。
+  *   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。
-*   **典型应用**：走迷宫、八皇后问题、数独。
+  *   **典型应用**：走迷宫、八皇后问题、数独。
 <html>

Detach Close

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

差别

该主题尚不存在

张叶安的博客