1.06
人生的成长，始于自我觉醒；人生的进步，始于改变自己
花生十三：逻辑论证之归因论证
题型分类：归因论证可分为实验对比归因、时间对比归因、直接根本原因三类，其中，对比归因既是重点也是难点，这类题目学员们普遍未找到解题思路，但如果“开窍”，是可以“秒杀”题型。
提问方法：绝大多数为“以下哪项如果为真，最能削弱上述结论？”；少数为“以下哪项如果为真,最能质疑研究人员的解释？”，后者更加简单，抓住“解释”即可。
质疑方式：常见有另有他因、因果倒置、否定此因三种。其中，另有他因需注意“回到实验中”（极少数会根据结果重新分组），因果倒置需要注意时间先后（本质为原因在结果之后，不能是此原因导致了结果）。
另有他因
易错答案：A
注意点：第二组的比例比第一组多两倍！！！比例！！！
正确选项：B
另有他因！！！
正确选项：C
另有他因，因为HEV便宜，并不是它操作便捷！
易错答案：A 伪他因，没有回归实验
正确答案：D
正确答案：B
正确答案：C
正确答案：D
正确答案：C
正确答案：B
正确选项：B
因果倒置质疑
因果倒置是一种在相对确定的条件下把原因和结果相互颠倒，视结果为原因和视原因为结果而引起的谬误。
正确答案：B
软考
1 排序算法
排序算法的稳定性是指将待排序列排序后，能确保排序码中的相对位置保持不变。（ ）是稳定的排序算法。
A 冒泡排序
B 快速排序
C 堆排序
D 简单选择排序
| 排序算法 | 稳定性 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 基本原理 | 举例 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 稳定 | O(n²) | O(n²) | O(1) | 比较相邻元素，如果顺序不对就交换，每次遍历都将最大（或最小）的元素“冒泡”到最后。 | [5, 2, 1, 4] -> [2, 1, 4, 5] -> [1, 4, 2, 5] -> [1, 2, 4, 5] (逐步将最大值冒泡到末尾) |
| 插入排序 | 稳定 | O(n²) | O(n²) | O(1) | 将未排序的元素逐个插入到已排序的序列中，保持已排序序列的有序性。 | [5, 2, 4, 1] -> [2, 5, 4, 1] -> [2, 4, 5, 1] -> [1, 2, 4, 5] (逐步将元素插入到已排序部分) |
| 简单选择排序 | 不稳定 | O(n²) | O(n²) | O(1) | 每次遍历未排序序列，选择最小（或最大）的元素，放到已排序序列的末尾。 | [5, 2, 4, 1] -> [1, 2, 4, 5] (每次选择最小元素放到前面) |
| 快速排序 | 不稳定 | O(n log n) | O(n²) | O(log n) | 选择一个基准元素，将序列分成两部分，一部分小于基准，一部分大于基准，然后递归地对两部分进行排序。 | [5, 2, 4, 1, 6] -> [1, 2, 4, 5, 6] (选择 5 为基准，分成两部分，递归) |
| 归并排序 | 稳定 | O(n log n) | O(n log n) | O(n) | 将序列递归地分成两部分，分别排序，然后合并两个已排序的子序列。 | [5, 2, 4, 1] -> [5, 2], [4, 1] -> [2, 5], [1, 4] -> [1, 2, 4, 5] (先分割，再合并) |
| 堆排序 | 不稳定 | O(n log n) | O(n log n) | O(1) | 将序列构建成一个大顶堆（或小顶堆），然后将堆顶元素与最后一个元素交换，再调整堆结构，重复此过程。 | [5, 2, 4, 1] -> 堆化 -> [5, 4, 2, 1] -> 交换 -> [1, 4, 2, 5] -> 调整 -> ... -> [1, 2, 4, 5] (构建堆，调整堆) |
| 希尔排序 | 不稳定 | O(n^1.3 ~ n^2) | O(n^2) | O(1) | 插入排序的改进版本，通过设置不同的增量，将序列分成若干子序列，分别进行插入排序，逐步缩小增量，最终完成排序。 | [5, 2, 4, 1, 3] -> 按增量分组排序 -> ... -> [1, 2, 3, 4, 5] (分组插入排序) |
| 计数排序 | 稳定 | O(n + k) | O(n + k) | O(k) | 适用于范围较小的整数排序，统计每个元素出现的次数，然后根据次数将元素放回原序列。 | [2, 1, 2, 3] -> 计数 -> [1:1, 2:2, 3:1] -> [1, 2, 2, 3] (统计次数，放回) |
| 桶排序 | 稳定 | O(n + k) | O(n²) | O(n + k) | 将元素分配到不同的桶中，每个桶内部进行排序，然后按顺序合并所有桶。 | [5, 2, 8, 1] -> 放入桶 -> 各桶排序 -> 合并 (分配到桶，桶内排序，合并) |
| 基数排序 | 稳定 | O(nk) | O(nk) | O(n + k) | 按照元素的每一位（个位、十位、百位等）进行排序，从最低位到最高位。 | [170, 45, 75, 90, 802, 24, 2] -> 按个位排 -> 按十位排 -> 按百位排 -> [2, 24, 45, 75, 90, 170, 802] (按位排序) |
2 算法策略
在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适用（ ） 算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间,则采用的是（ ）算法策略。
A 分治
B 贪心
C 动态规则
D 回溯
常用算法策略总结
| 策略名称 | 核心思想 | 适用场景 | 优点 | 缺点 | 选择考虑因素 |
|---|---|---|---|---|---|
| 分治法 | 将一个复杂的问题分解成两个或多个相同或相似的子问题，再把子问题分解成更小的子问题，直到最后子问题可以简单地直接求解，最后将各个子问题的解合并得到原问题的解。 | 适用于可以分解成相互独立的子问题，且子问题与原问题性质相同的问题。如：归并排序、快速排序、二分查找、大整数乘法、矩阵乘法等。 | 可以有效降低问题的复杂度，将大规模问题转化为小规模问题，更容易解决；并行计算友好，可以提高计算速度。 | 需要递归，可能造成栈溢出；分解和合并的过程可能增加额外开销；并非所有问题都适合分治。 | 问题是否可以分解成独立的子问题？子问题是否与原问题性质相同？是否存在高效的合并方法？是否需要考虑递归带来的开销？ |
| 动态规划 | 将问题分解成相互重叠的子问题，并存储子问题的解，避免重复计算。通过定义状态和状态转移方程，自底向上求解问题。 | 适用于具有重叠子问题和最优子结构性质的问题。如：背包问题、最长公共子序列、最短路径问题、编辑距离等。 | 可以避免重复计算，提高效率；可以求解具有最优子结构的问题；通常可以得到全局最优解。 | 需要额外的空间存储子问题的解；状态定义和状态转移方程的设计较为复杂；并非所有问题都具有最优子结构。 | 问题是否具有重叠子问题？是否具有最优子结构性质？状态如何定义？状态转移方程如何设计？空间复杂度是否可接受？ |
| 贪心算法 | 在每一步选择中都采取在当前状态下最好或最优的选择，希望通过局部最优的选择达到全局最优。 | 适用于局部最优解可以导致全局最优解的问题。如：霍夫曼编码、最小生成树（Prim/Kruskal）、活动选择问题等。 | 实现简单，效率高；通常可以快速找到一个较好的解。 | 并非所有问题都适用，可能无法找到全局最优解；需要证明贪心选择的正确性。 | 问题是否满足贪心选择性质？选择的局部最优是否会导致全局最优？是否存在反例？ |
| 回溯法 | 通过尝试所有可能的解来找到问题的解。在搜索过程中，如果发现当前选择不能得到解，则回溯到上一步，尝试其他选择。 | 适用于需要搜索所有可能解的问题，如：八皇后问题、数独、迷宫问题、组合问题、排列问题等。 | 可以找到所有解或最优解；通用性强，适用于各种问题。 | 效率较低，时间复杂度高，可能超时；需要仔细设计剪枝策略以减少搜索空间。 | 问题是否需要搜索所有可能解？时间复杂度是否可接受？是否存在有效的剪枝策略？ |
| 枚举法 | 尝试所有可能的解，逐个验证是否满足条件。 | 适用于问题规模较小，解空间有限的问题。 | 实现简单，容易理解；可以得到所有解。 | 效率较低，时间复杂度高，不适用于大规模问题；可能需要大量的计算资源。 | 问题规模是否很小？解空间是否有限？是否存在更高效的算法？ |
| 搜索算法 | 在解空间中搜索问题的解，如深度优先搜索（DFS）和广度优先搜索（BFS）。 | 适用于需要遍历解空间的问题。DFS适用于深度优先的探索，BFS适用于广度优先的探索。如：图的遍历、迷宫问题、树的遍历等。 | DFS占用空间较小，容易实现；BFS可以找到最短路径。 | DFS可能陷入死循环，需要注意边界条件；BFS占用空间较大。 | 问题是否需要遍历解空间？需要深度优先还是广度优先的搜索？空间复杂度是否可接受？是否存在死循环的风险？ |
选择算法策略的考虑因素：
-
问题是否可以分解成子问题？子问题之间是否存在重叠？
-
可以分解成子问题：
意味着问题可以拆分成更小、更易处理的部分。
- 例子： 归并排序将一个数组不断二分，直到每个子数组只有一个元素。
-
子问题之间存在重叠：
意味着在解决不同子问题时，可能会重复计算某些相同的子问题。
- 例子： 计算斐波那契数列
fib(n) = fib(n-1) + fib(n-2)，计算fib(5)需要计算fib(4)和fib(3)，而计算fib(4)又需要计算fib(3)和fib(2)，fib(3)被重复计算。
- 例子： 计算斐波那契数列
-
应用：
- 如果问题可以分解且子问题不重叠，可以考虑分治法。
- 如果子问题重叠，且需要最优解，可以考虑动态规划。
-
-
问题是否具有最优子结构？
-
最优子结构：
意味着问题的最优解可以通过其子问题的最优解构建得出。
- 例子： 求最短路径，从 A 到 C 的最短路径必然经过 B，且 A 到 B 以及 B 到 C 的路径也必须是最短路径。
-
应用：
- 具有最优子结构的问题通常可以使用动态规划或贪心算法解决。
- 动态规划适用于子问题重叠的情况，而贪心算法适用于局部最优能导致全局最优的情况。
-
-
是否需要找到所有解？还是只需要一个解？或者最优解？
-
所有解：
需要找出满足问题的所有可能情况。
- 例子： 八皇后问题，需要找到所有皇后互不攻击的摆放方式。
-
一个解：
只需要找到一个满足条件的解即可。
- 例子： 在迷宫中找到一条出口路径。
-
最优解：
需要找到满足条件的最优解，例如最短路径，最大利润等。
- 例子： 背包问题，需要在背包容量限制下，装入价值最高的物品。
-
应用：
- 需要所有解，通常考虑回溯法或枚举法。
- 只需要一个解，可以考虑搜索算法（DFS/BFS）。
- 需要最优解，通常考虑动态规划、贪心算法或搜索算法（如 A* 算法）。
-
-
是否存在局部最优解可以导致全局最优解？
-
局部最优解导致全局最优解：
指的是在每一步都选择当前最佳的选择，最终可以得到问题的全局最优解。
- 例子： 霍夫曼编码，每次选择频率最小的两个节点合并，最终可以得到最优的编码方案。
-
应用：
- 如果存在这种特性，可以考虑使用贪心算法。但需要证明贪心选择的正确性。
-
数据规模
数据量大小直接影响算法的时间和空间复杂度。
- 数据量小，可以选择简单易懂的算法，如枚举法，插入排序。
- 数据量大，需要选择高效的算法，如分治法、动态规划、快速排序、归并排序。
- 大规模数据通常需要高效的算法，如分治法、动态规划。
- 分治法可以将问题分解成小问题，适合并行计算，提高效率。
- 动态规划可以避免重复计算，降低时间复杂度。
