数据结构:绪论

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
数据结构:绪论 [2025/12/11 16:20] – [3. 存储结构：数据在“内存”中的物理形态] 张叶安数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安
行 322: 行 322:
 === 1.1 常见复杂度详解 === === 1.1 常见复杂度详解 ===
  
-*   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。 +  *   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。 
-    <code c>+<code c>
     int n = 10000;     int n = 10000;
     x = n + 1; // 无论n多大，这行只执行一次     x = n + 1; // 无论n多大，这行只执行一次
-    </code> +</code> 
-*   **$O(n)$ 线性阶**：一层循环。 +  *   **$O(n)$ 线性阶**：一层循环。 
-    <code c>+<code c>
     for(int i=0; i<n; i++) { ... }     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 i=0; i<n; i++) {
         for(int j=0; j<n; j++) { ... }         for(int j=0; j<n; j++) { ... }
     }     }
-    </code> +</code> 
-*   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。 +  *   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。 
-    <code c>+<code c>
     while(n > 1) {     while(n > 1) {
         n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了         n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了
     }     }
-    </code>+</code>
  
 ===== 第三部分：五大常用算法思想详解 ===== ===== 第三部分：五大常用算法思想详解 =====
行 350: 行 350:
 ==== 1. 穷举法 (Brute Force) ==== ==== 1. 穷举法 (Brute Force) ====
  
-*   **别名**：暴力破解法。 +  *   **别名**：暴力破解法。 
-*   **核心**：列出所有可能的情况，逐一验证。 +  *   **核心**：列出所有可能的情况，逐一验证。 
-*   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。 +  *   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。 
-*   **缺点**：效率极低。 +  *   **缺点**：效率极低。 
-*   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。+  *   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
  
 ==== 2. 分治法 (Divide and Conquer) ==== ==== 2. 分治法 (Divide and Conquer) ====
  
-*   **核心口诀**：**分而治之，各个击破**。 +  *   **核心口诀**：**分而治之，各个击破**。 
-*   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。 +  *   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。 
-*   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。+  *   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
  
 <html> <html>
行 408: 行 408:
 ==== 3. 动态规划 (Dynamic Programming, DP) ==== ==== 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)$     *   求第 5 个数：$F(5) = F(4) + F(3)$
     *   求 $F(4)$ 时需要算 $F(3) + F(2)$。     *   求 $F(4)$ 时需要算 $F(3) + F(2)$。
行 480: 行 480:
 ==== 4. 贪心算法 (Greedy) ==== ==== 4. 贪心算法 (Greedy) ====
  
-*   **核心**：**活在当下**。 +  *   **核心**：**活在当下**。 
-*   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。 +  *   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。 
-*   **案例：找零钱**+  *   **案例：找零钱**
     *   问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。     *   问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。
     *   贪心策略：优先用面值最大的。     *   贪心策略：优先用面值最大的。
     *   步骤：     *   步骤：
-        1.  66 < 100，跳过。 +        *  66 < 100，跳过。 
-        2.  66 >= 50，**给一张 50**。剩 16。 +        *  66 >= 50，**给一张 50**。剩 16。 
-        3.  16 < 20，跳过。 +        *  16 < 20，跳过。 
-        4.  16 >= 10，**给一张 10**。剩 6。 +        *  16 >= 10，**给一张 10**。剩 6。 
-        5.  6 >= 5，**给一张 5**。剩 1。 +        *  6 >= 5，**给一张 5**。剩 1。 
-        6.  **给一张 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) ==== ==== 5. 回溯法 (Backtracking) ====
  
-*   **核心**：**试错与回退**。 +  *   **核心**：**试错与回退**。 
-*   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。 +  *   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。 
-*   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。 +  *   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。 
-*   **典型应用**：走迷宫、八皇后问题、数独。+  *   **典型应用**：走迷宫、八皇后问题、数独。
  
 <html> <html>
Detach Close

该主题尚不存在

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

  • 数据结构/绪论.1765441243.txt.gz
  • 最后更改: 2025/12/11 16:20
  • 由 张叶安