skip to content
Logo Logo ZhenXI Blog

1.06

人生的成长，始于自我觉醒；人生的进步，始于改变自己

花生十三：逻辑论证之归因论证

题型分类：归因论证可分为实验对比归因、时间对比归因、直接根本原因三类，其中，对比归因既是重点也是难点，这类题目学员们普遍未找到解题思路，但如果“开窍”，是可以“秒杀”题型。

提问方法：绝大多数为“以下哪项如果为真，最能削弱上述结论？”；少数为“以下哪项如果为真,最能质疑研究人员的解释？”，后者更加简单，抓住“解释”即可。

质疑方式：常见有另有他因、因果倒置、否定此因三种。其中，另有他因需注意“回到实验中”（极少数会根据结果重新分组），因果倒置需要注意时间先后（本质为原因在结果之后，不能是此原因导致了结果）。

image-20250106145917920

另有他因

image-20250106153450927

易错答案：A

注意点：第二组的比例比第一组多两倍！！！比例！！！

正确选项：B

另有他因！！！

image-20250106154640602

正确选项：C

另有他因，因为HEV便宜，并不是它操作便捷！

image-20250106155443329

易错答案：A 伪他因，没有回归实验

正确答案：D

image-20250106160430683

正确答案：B

image-20250106161613219

正确答案：C

image-20250106170955089 image-20250106171015514

正确答案：D

image-20250106171604938

正确答案：C

image-20250106185521541

正确答案：B

image-20250106190916119 image-20250106191057137

正确选项：B

因果倒置质疑

因果倒置是一种在相对确定的条件下把原因和结果相互颠倒，视结果为原因和视原因为结果而引起的谬误。

image-20250106191404454 image-20250106191731945 image-20250106191936071

正确答案：B

image-20250106192228593

软考

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占用空间较大。问题是否需要遍历解空间？需要深度优先还是广度优先的搜索？空间复杂度是否可接受？是否存在死循环的风险？

选择算法策略的考虑因素：

  1. 问题是否可以分解成子问题？子问题之间是否存在重叠？

    • 可以分解成子问题：

      意味着问题可以拆分成更小、更易处理的部分。

      • 例子： 归并排序将一个数组不断二分，直到每个子数组只有一个元素。

    • 子问题之间存在重叠：

      意味着在解决不同子问题时，可能会重复计算某些相同的子问题。

      • 例子： 计算斐波那契数列 fib(n) = fib(n-1) + fib(n-2)，计算 fib(5) 需要计算 fib(4) 和 fib(3)，而计算 fib(4) 又需要计算 fib(3) 和 fib(2)，fib(3) 被重复计算。

    • 应用：

      • 如果问题可以分解且子问题不重叠，可以考虑分治法。
      • 如果子问题重叠，且需要最优解，可以考虑动态规划。

  2. 问题是否具有最优子结构？

    • 最优子结构：

      意味着问题的最优解可以通过其子问题的最优解构建得出。

      • 例子： 求最短路径，从 A 到 C 的最短路径必然经过 B，且 A 到 B 以及 B 到 C 的路径也必须是最短路径。

    • 应用：

      • 具有最优子结构的问题通常可以使用动态规划或贪心算法解决。
      • 动态规划适用于子问题重叠的情况，而贪心算法适用于局部最优能导致全局最优的情况。

  3. 是否需要找到所有解？还是只需要一个解？或者最优解？

    • 所有解：

      需要找出满足问题的所有可能情况。

      • 例子： 八皇后问题，需要找到所有皇后互不攻击的摆放方式。

    • 一个解：

      只需要找到一个满足条件的解即可。

      • 例子： 在迷宫中找到一条出口路径。

    • 最优解：

      需要找到满足条件的最优解，例如最短路径，最大利润等。

      • 例子： 背包问题，需要在背包容量限制下，装入价值最高的物品。

    • 应用：

      • 需要所有解，通常考虑回溯法或枚举法。
      • 只需要一个解，可以考虑搜索算法（DFS/BFS）。
      • 需要最优解，通常考虑动态规划、贪心算法或搜索算法（如 A* 算法）。

  4. 是否存在局部最优解可以导致全局最优解？

    • 局部最优解导致全局最优解：

      指的是在每一步都选择当前最佳的选择，最终可以得到问题的全局最优解。

      • 例子： 霍夫曼编码，每次选择频率最小的两个节点合并，最终可以得到最优的编码方案。

    • 应用：

      • 如果存在这种特性，可以考虑使用贪心算法。但需要证明贪心选择的正确性。

数据规模

数据量大小直接影响算法的时间和空间复杂度。

  • 数据量小，可以选择简单易懂的算法，如枚举法，插入排序。
  • 数据量大，需要选择高效的算法，如分治法、动态规划、快速排序、归并排序。
  1. 大规模数据通常需要高效的算法，如分治法、动态规划。
    • 分治法可以将问题分解成小问题，适合并行计算，提高效率。
    • 动态规划可以避免重复计算，降低时间复杂度。