软件设计师-第八章算法基础

第八章算法基础

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作

5个重要特性：有穷性、确定性、可行性、输入、输出

1. 时间复杂度

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

2. 空间复杂度

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

3. 递归

3.1 主定理

设a≥1和b>1为常数，设f(n)为一函数，T(n)由递归式 $T(n)=aT(\frac{n}{b})+f(n)$
其中 $\frac{n}{b}$ 指$\left\lfloor \frac{n}{b}\right\rfloor $和$ \left\lceil \frac{n}{b}\right\rceil $，可以证明，略去上下取整不会对结果造成影响。

那么 $T(n)$ 可能有如下的渐进界：

若 $f(n)<n^{log_b^a}$ ,且是多项式的小于。即

$\exists\ \varepsilon>0$ ,有 $\mathrm{f(n)=\Theta(n^{log_{b}^{a}-\varepsilon})}$ 则 $\mathrm{T}(\mathrm{n})=\Theta(n^{log_b^a})$
若 $f(n)=\Theta(n^{\log_ba}\lg^kn)$ ，则 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$
若 $f(n)>n^{log_{b}^{a}}$ ,且是多项式的大于。即

$\exists\ \varepsilon>0$ , 有 $f(n)=\:\Omega\left(n^{log_{b}^{a}+\varepsilon}\right)$ ,

且对 $\forall \ c<1$ 与所有足够大的n,有 $\mathrm{af(\frac{n}{b})\leq cf(n)}$ ,则 $\mathrm{T(n)=\Theta(f(n))}$

4. 常见算法

算法名称	关键点	特征	典型问题
分治法	递归技术	把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。	归并排序、快速排序、二分搜索
贪心法	一般用于求满意解，特殊情况可求最优解（部分背包）	局部最优，但整体不见得最优。每步有明确的，既定的策略。	背包问题（如装箱）、多机调度、找零钱问题
动态规划法	最优子结构，递归式，中间解数组	划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。	矩阵乘法、背包问题 LCS最长公共子序列
回溯法	探索和回退	系统的搜索一个问题的所有解或任一解。有试探和回退的过程。	N皇后问题、迷宫、背包问题

4.1 算法策略判断

回溯，有尝试探索和回退的过程。这个比较好识别。
分治，分治与动态规划法其实最难区分，分治不好解决的问题，从而记录中间解，

解决问题，有了动态规划法，但是在软设考试中，分治目前只有二分的思想，二

分以外的思想都用动态规划法解决了。二分的时间复杂度，与 $O(nlog_{2}^{n})$ 相关，注

意有没有外层嵌套循环。（结合归并排序、快速排序的过程，也是二分的）
动态规划法，有递归式，经常考查递归式，
- 此时自底向上实现时，中间解基本上是查表可得的，所以时间复杂度一般是 $O(n^k)$ ,具体k是多少，根据for循环的嵌套。此时循环变量能够看到，是从0或1开始，到结束，这种情况就是从小规模到大规模，自底向上的。
- 如果用到自顶向下，其实跟分治的实现就差不多了，查表的意义基本上可以忽略不计了，时间复杂度为 $O(2^n)$ ,递归的变量一般由n开始，向1缩小，所以是大规模到小规模，也就是自顶向
（一般动态规划法涉及递归式，递归式还会经常用在代码填空中让大家补充缺失的填空，然后会有“最优子结构”的描述，会有表（数组）记录中间解。)
贪心法，有时候也会出现“最优子结构”的描述，但是没有递归式。考虑的是当前最优，求得的是满意解

(特殊情况下，贪心法有时候得到的也可以是最优解，比如部分背包问题)

4.1 贪心法

贪心法：总是做出在当前来说是最好的选择,而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解

局部贪心，只针对当前的步骤取最优，而非整体考虑
判断此类算法，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的

一般情况下，贪心算法的适用情况分以下两种。

可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的。

4.2 分治法

分治法：对于一个规模为n的问题，若该问题可以容易地解决则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解.

一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。

问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
子问题的解可以合并：原问题的解通过合并子问题的解得来。

递归：指子程序（函数）直接调用自己活通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法
递归两个基本要素：
- 边界条件（确定递归何时终止，即递归出口）
- 递归模式（大问题如何分解成小问题，即递归体）
步骤：
- 分解（将原问题分解成一系列子问题）
- 求解（递归地求解各子问题，若子问题足够小，则直接求解）
- 合并（将子问题的解合并成原问题的解）
凡是涉及到分组解决的都是分治法（二分查找、归并排序等)

4.3 回溯法

回溯法：有 “通用的解题法” 之称，可以系统地搜索一个问题的所有解或任一解。之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。

在包含问题的所有解的解空间树中，

按照深度优先的策略，从根节点触发搜索解空间树。
搜索至任一结点时，总是先判断该结点是否肯定不包含问题的解
如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；
否则，进入该子树；继续按深度优先的策略进行搜索
可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层.
一般用于解决迷宫类的问题

优点与局限性

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。

然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。

时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。

剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。

4.4 动态规划法

动态规划法：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解.

本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间不是相互独立的，并且不全都相同。
常用于求解具有某种最优性质的问题
此算法会将大量精力放在前期构造表格上面，其会对每一步，列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，是通过查询这张表来得到的动态规划法不但每一步最优，全局也最优

4.5 算法对比

我们学习了动态规划是如何通过子问题分解来求解原问题的。实际上，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。

分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。

实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。

贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同。

动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。

3. 查找算法

3.1 顺序查找

将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败顺序查找的时间复杂度为：时间复杂度为 $O(n)$

3.2 二分查找

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
时间复杂度为 𝑂(log⁡𝑛) ：在二分循环中，区间每轮缩小一半，因此循环次数为 log2⁡𝑛 。
空间复杂度为 𝑂(1) ：指针 𝑖 和 𝑗 使用常数大小空间。

优势

二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势。
二分查找无须额外空间。相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间。

局限

二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。
二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 𝑛 较小时，线性查找反而比二分查找更快。

3.3 哈希表

散列（哈希）表：根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置。

在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。

线性查找：以时间换空间
哈希查找：以空间换时间

3.3 对比查找算法

线性搜索

通用性较好，无须任何数据预处理操作。假如我们仅需查询一次数据，那么其他三种方法的数据预处理的时间比线性搜索的时间还要更长。
适用于体量较小的数据，此情况下时间复杂度对效率影响较小。
适用于数据更新频率较高的场景，因为该方法不需要对数据进行任何额外维护。

二分查找

适用于大数据量的情况，效率表现稳定，最差时间复杂度为 𝑂(log⁡𝑛) 。
数据量不能过大，因为存储数组需要连续的内存空间。
不适用于高频增删数据的场景，因为维护有序数组的开销较大。

哈希查找

适合对查询性能要求很高的场景，平均时间复杂度为 𝑂(1) 。
不适合需要有序数据或范围查找的场景，因为哈希表无法维护数据的有序性。
对哈希函数和哈希冲突处理策略的依赖性较高，具有较大的性能劣化风险。
不适合数据量过大的情况，因为哈希表需要额外空间来最大程度地减少冲突，从而提供良好的查询性能。

树查找

适用于海量数据，因为树节点在内存中是分散存储的。
适合需要维护有序数据或范围查找的场景。
在持续增删节点的过程中，二叉搜索树可能产生倾斜，时间复杂度劣化至 𝑂(𝑛) 。
若使用 AVL 树或红黑树，则各项操作可在 𝑂(log⁡𝑛) 效率下稳定运行，但维护树平衡的操作会增加额外的开销。

4. 排序算法

排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

4.1 算法评价

运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。
就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。
自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。
是否基于比较：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 𝑂(𝑛log⁡𝑛) 。而非比较排序不使用比较运算符，时间复杂度可达 𝑂(𝑛) ，但其通用性相对较差。

4.2 排序分类

排序的算法：

插入类排序：直接插入排序、希尔排序
交换类排序：冒泡排序、快速排序
选择类排序：简单选择排序、堆排序
归并排序
基数排序

4.3 选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

算法特征

**时间复杂度为： $O(n^{2})$ **
非自适应排序
空间复杂度为 $O(1)$
原地排序
非稳定排序

4.4 冒泡排序

冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

算法特征

**时间复杂度为： $O(n^{2})$ **
自适应排序
空间复杂度为 $O(1)$
原地排序
稳定排序

4.5 插入排序

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

算法特征

**时间复杂度为： $O(n^{2})$ **
自适应排序
空间复杂度为 $O(1)$
原地排序
稳定排序

对比

插入排序的时间复杂度为 𝑂(𝑛2) ，而快速排序的时间复杂度为 𝑂(𝑛log⁡𝑛) 。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。
虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$ $O (n^{2})$ ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。
- 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
- 选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
- 选择排序不稳定，无法应用于多级排序。

4.6 快速排序

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

算法特征

**时间复杂度为： $O(nlogn)$ **
非自适应排序
空间复杂度为 $O(1)$
原地排序
非稳定排序

4.7 归并排序

归并排序（merge sort）是一种基于分治策略的排序算法，包含两个阶段

划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

算法特征

**时间复杂度为： $O(nlogn)$ **
非自适应排序
空间复杂度为 $O(1)$
原地排序
稳定排序

对于链表，归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 $O(1)$

4.8 堆排序

堆排序（heap sort）是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。

输入数组并建立小顶堆，此时最小元素位于堆顶。
不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

算法特征

**时间复杂度为： $O(nlogn)$ **
非自适应排序
空间复杂度为 $O(1)$
原地排序
非稳定排序

4.9 桶排序

桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

算法特征

**时间复杂度为： $O(n+k)$ **
空间复杂度为 $O(n+k)$
非原地排序
桶排序是否稳定取决于排序桶内元素的算法是否稳定。

4.10 计数排序

计数排序（counting sort）通过统计元素数量来实现排序，通常应用于整数数组。

算法特征

**时间复杂度为： $O(n+m)$ **
非自适应排序
空间复杂度为 $O(n+m)$
非原地排序
稳定排序

局限性

计数排序只适用于非负整数
计数排序适用于数据量大但数据范围较小的情况。

4.11 基数排序

基数排序（radix sort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。

算法特征

**时间复杂度为： $O(nk)$ **
非自适应排序
空间复杂度为 $O(n+d)$
非原地排序
稳定排序

数据量为 𝑛、数据为 𝑑 进制、最大位数为 𝑘

第八章 算法基础

1. 时间复杂度

2. 空间复杂度

3. 递归

3.1 主定理

4. 常见算法

4.1 算法策略判断

4.1 贪心法

4.2 分治法

4.3 回溯法

4.4 动态规划法

4.5 算法对比

3. 查找算法

3.1 顺序查找

3.2 二分查找

3.3 哈希表

3.3 对比查找算法

4. 排序算法

4.1 算法评价

4.2 排序分类

4.3 选择排序

4.4 冒泡排序

4.5 插入排序

4.6 快速排序

4.7 归并排序

4.8 堆排序

4.9 桶排序

4.10 计数排序

4.11 基数排序

第八章算法基础