Update 01.Enumeration-Algorithm.md

杨世超 · 杨世超 · commit dce7cd0fc5f2 · 2022-03-29T17:25:52.000+08:00
diff --git a/Contents/09.Algorithm-Base/01.Enumeration-Algorithm/01.Enumeration-Algorithm.md b/Contents/09.Algorithm-Base/01.Enumeration-Algorithm/01.Enumeration-Algorithm.md
@@ -18,10 +18,13 @@
 
 1. 确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
 2. 一一枚举可能的情况，并验证是否是问题的解。
-3. 从下面几个方面考虑提高算法的效率：
-   1. 抓住问题状态的本质，尽可能缩小问题状态空间的大小。
-   2. 加强约数条件，缩小枚举范围。
-   3. 根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。
+3. 考虑提高枚举算法的效率。
+
+我们可以从下面几个方面考虑提高算法的效率：
+
+1. 抓住问题状态的本质，尽可能缩小问题状态空间的大小。
+2. 加强约束条件，缩小枚举范围。
+3. 根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。
 
 ## 3. 枚举算法的应用
 
@@ -82,6 +85,8 @@ class Solution:
 
 考虑到如果 `i` 是 `x` 的因数，则 $\frac{x}{i}$ 也必然是 `x` 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 `x` 是否为质数时，只需要枚举 $[2, \sqrt x]$ 中的所有数即可。
 
+利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$，检查 `n` 个数的整体时间复杂度为 $O(n \sqrt{n})$。
+
 #### 3.2.4 代码
 
 ```Python
@@ -124,6 +129,8 @@ class Solution:
 
 在遍历枚举的同时，我们维护一个用于统计平方和三元组数目的变量 `cnt`。如果符合要求，则将计数 `cnt` 加 `1`。最终，我们返回该数目作为答案。
 
+利用枚举算法统计平方和三元组数目的时间复杂度为 $O(n^2)$。
+
 - 注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于 `1`，所以我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来代替 $\sqrt{a^2 + b^2}$。
 
 #### 3.3.4 代码
@@ -165,16 +172,25 @@ class Solution:
 | 对应选取状态            | 选取 | 选取 | 选取 | 选取 | 选取 |
 | 二进制数对应位数        |  1   |  1   |  1   |  1   |  1   |
 
-再比如二进制数 `10101` 就表示选取集合的第 `0` 位、第 `2` 位、第 `5` 为元素，也就是集合 `{5, 3, 1}`。如下表所示：
+再比如二进制数 `10101` 就表示选取集合的第 `0` 位、第 `2` 位、第 `5` 位元素，也就是集合 `{5, 3, 1}`。如下表所示：
 
-| 集合 S 对应位置（下标） |  4   |  3   |  2   |  1   |  0   |
-| :---------------------- | :--: | :--: | :--: | :--: | :--: |
-| 对应选取状态            | 选取 | 选取 | 选取 | 选取 | 选取 |
-| 二进制数对应位数        |  1   |  1   |  1   |  1   |  1   |
+| 集合 S 对应位置（下标） |  4   |   3    |  2   |   1    |  0   |
+| :---------------------- | :--: | :----: | :--: | :----: | :--: |
+| 对应选取状态            | 选取 | 未选取 | 选取 | 未选取 | 选取 |
+| 二进制数对应位数        |  1   |   0    |  1   |   0    |  1   |
+
+再比如二进制数 `01001` 就表示选取集合的第 `0` 位、第 `3` 位元素，也就是集合 `{5, 2}`。如下标所示：
+
+| 集合 S 对应位置（下标） |   4    |  3   |   2    |   1    |  0   |
+| :---------------------- | :----: | :--: | :----: | :----: | :--: |
+| 对应选取状态            | 未选取 | 选取 | 未选取 | 未选取 | 选取 |
+| 二进制数对应位数        |   0    |  1   |   0    |   0    |  1   |
+
+通过上面的例子我们可以得到启发：对于长度为 `5` 的集合 `S` 来说，我们只需要从 `00000` ~ `11111` 枚举一次（对应十进制为 $0 \sim 2^4 - 1$）即可得到长度为 `5` 的集合 `S` 的所有子集。
 
-通过上面的例子我们可以得到启发，对于长度为 `5` 的集合 `S` 来说，我们只需要从 `00000` ~ `11111` 枚举一次（对应十进制为 $0 \sim 2^4 - 1$）即可得到长度为 `5` 的集合 `S` 的所有子集。
+我们将上面的例子拓展到长度为 `n` 的集合 `S`。可以总结为：
 
-拓展到长度为 `n` 的集合 `S`，则需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到所有的子集。
+- 对于长度为 `5` 的集合 `S` 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到所有的子集。
 
 ### 4.2 二进制枚举子集代码
 
