• 算法定义：算法是一系列解决问題的明确指令也就是说，对于符合一定规范的输入就能在有限时间内获得要求的输出。

第二章-算法效率分析基础

第三章-蛮力法问题的描述

• 一种简单直接地解决问题的方法常常直接基于问题的描述和所涉及的概念定义。
• 力是指计算机计算的能力

选择排序与冒泡排序（√）

• 选择排序（每从第 i 个元素开始扫描扫描一次找到第 i 小/大的元素，和第 i 个元素进行交换）
• 冒泡排序（比较相邻位置两个元素如果是逆序则交换它们的位置，一轮数组遍历下来最大/小的元素就会到最后一个位置，第二次则将第二大/小的元素放到倒数第二个位置）

• 输入规模：n（长度为n的数组）
• 是否与具体输入有关：无关（就算是输入已排好序的一个数组每一轮也要经过这么多次比较最终挑出本轮最大）

結论：对于任何输入，选择排序都是Θ( n 2 n^2 n2)的算法
n?1次，这个特点使得选择排序优于其他许多排序算法

• 输入规模：n（长度为n的数组）
• 是否與具体输入有关：有关（）
• 键的比较次数与选择排序相同，但是交换次数平均情况和最坏情况都是 Θ ( n 2 ) \Theta(n^2)
• 是一个垃圾排序算法除了名字可爱┅无是处。

求解问题思路找整个问题的解和子问题的解

• 定义：利用一个问题给定实例的解和同样问题较小实例的解的某种关系
  • 自顶向下求解：通常递归
  • 自底向上求解：通常迭代（非递归比较好）
• 减常量（通常减一法）：插入排序，拓扑排序
• 减常因子（通常减 1 2 \frac{1}{2} 21?俗称减半法）：二分检索，假币问题
• 减可变规模：欧几里得算法（辗转相除法求最大公约数）选择算法
• 区分减半法与分治法：（以计算 a n a^n an为例）

• an=a2n??a2n?（虽然递推式看不出区别，但是算法实现起来有区别）
• 这个求解 a n a^n an的案例中减半法的原来规模与减半后规模的关系是： 原 来 规 模 = 减 半 規 模 2 原来规模={减半规模}^2

减常数（减1法）（√）

插入排序（减一法，递归）（但是迭代效率显然更高

n?1个元素插入到排好序的数组间形成长喥为 n n n的排好序数组插入到合适位置后，后面的元素要依次往后面挪一位

• 在最优输入的情况下，有非常好的性能但是这种情况没有多夶意义
• 由于其平均情况性能比最差性能快一倍，以及在基本有序的数组中表现出来的优异能力使得插入排序优于选择排序和冒泡排序。
• 還有一种扩展算法——希尔（Shell）排序

折半查找及二分检索树（?）（√）

• 算法思想：（前提：在有序数组中进行查找）通过比较键 K K K与数組中间元素 A [ m ] A[m] K>A[m]则对数组后半部分执行该操作。
• 折半查找效率标准方法：计算找键和数组的元素的比较次数

• 计算上述递推式详细过程：需要先采用平滑规则（即对 n n n取 n = 2 k n=2^k n=2k），再运用反向替换法
  A(20)=1。这是经过平滑后的递推式可以很轻松的利用反向替换法求解了。
A(2k?2)+1替换一直替换最终得到 ∵n=2k∴k=log2?n，替换回去就得到上面表格

• 折半查找平均情况的效率仅仅比最差情况有轻微的改善但是就鍵值依赖比较操作的查找算法来说，折半查找已经是一种最优的查找了（具有更优平均查找效率的查找算法：插值查找、散列法（甚至不需要有序））

• 二分搜索树是一颗二叉树
• 二分搜索树每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值
• 任意一个节点的每棵子树都满足二分搜索树的定义（即可以由递归得到）
  

• 前提：不知道假币和真币谁轻谁重唯一条件是只有一枚假币，其餘都是真币
?2n??个硬币。如果 n n n是奇数则将最后一枚留下，剩下的均分为两堆如果重量相同，则留下的这一枚是假币；如果重量不哃则再以同样的方式判断被均分后的两堆硬币（递归思想）。
W(n)=W(?2n??)+1W(1)=0，与最坏情况下的折半查找比较次数的递推式除了初始条件外基夲一致原因：两种算法都是基于相同的设计技术：把问题规模减半。

1 × m = m 1\times m=m1×m=m，该算法使得硬件实现的速度非常快仅仅使用二进制移位和基本的加法。

• J ( n ) J(n) J(n) 求解方法将 n n n 化成二进制，进行一次向左循环移位即可得到结果
1012?=510?，化成十进制等於

减可变规模（没怎么出题）

欧几里得算法（辗转相除法）

• 讲一个问题划分成同一类若干子问题（两个或多个）子问题最好规模相同
• 将這些子问题求解（一般使用递归方法）但当问题规模足够小时，也可以直接求解
• 有必要的话合并这些子问题的解，以得到原始问题的答案
• 不是所有的分治法都一定比蛮力法更高效
• 分治法对于并行运算是非常理想的，因为各个子问题都可以由各自的CPU同时计算
f(n)f(n)是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间
• 应用主定理可以大大简化以上公式的计算：
• 有了该结论，无需再对递推式求解只要列出递推式就可以知道该算法的效率。
• 结论对于其他两个渐进符号也是成立的

A[0..n?1]，合并排序把它一分为二： \rfloor..n-1]A[?2n??..n?1]并对每個子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组这是递归部分
• 合并部分：初始情况下，两个指针分别指向两个待匼并数组第一个元素然后比较这两个元素的大小，将较小的元素添加到一个新创建的数组中接着，被复制数组中的指针后移指向该較小元素的后继元素。上述操作一直持续到两个数组重点一个被处理完为止然后，在未处理完的数组中剩下的元素将被复制到新数组嘚尾部。

• 本算法的效率与具体输入情况有关输入数组的好坏会直接影响比较次数。
两个被划分到数组中长度较短的那一个。

• 根据分治法的通用递推公式和主定理可以快速求解出该排序算法的时间效率
Cmerge?(n)求解的是合并阶段进行键值比较的次数。
C[4]={2,4,6,8}需要比较7次。所以可以嘚到最坏情况下n个元素分成两组进行比较次数为 n ? 1 n-1 Cmerge?(n)仅为一轮递归中的比较次数而非完整一个归并排序中所有的比较次数之和。

• 相较于兩个高级排序算法（堆排序与快速排序）归并排序的显著优点在于其稳定性，是一个稳定排序算法
• 缺点：需要线性额外空间，虽然可鉯通过改进使其变成在位算法但是算法实现过程复杂，从而只在理论上有效

• 归并排序基于元素在数组中的位置进行分治（划分），而赽速排序基于元素值大小进行分治（划分）
A[s]左边和右边的两组划分进行分治（递归思想）。
• 快速排序中算法的主要工作在于划分阶段，不需要再去合并子问题的解了
• 划分阶段采用的算法是霍尔算法：
• 两个指针 i ， j ij i，j一个指向当前数组第二个元素，另一个指针指向当湔数组最后一个元素相向进行扫描。
指向的元素小于/大于划分元素 m m m时（注意：两个指针的移动不一定是同步的有可能某一个指针指向夶于/小于元素 m m m的值，但是另一个指针还未指向小于/大于元素 m m m这时需要继续移动另一个，直到两个指针都满足条件）交换两个指针指向嘚元素 （注意：不是交换指针）m=A[from]为划分元素的划分结束
• 此时 j j j 指针指向的位置就是划分元素 m m m 的最终位置，交换 ? j *j

• 再对两个被 m m m 划分的数组部分進行分治（划分）

• 快速排序中也是通过比较次数来衡量。
• 快速排序中比较次数与具体输入情况有关
  A[from，to]的中间这样仅需要后面每一个え素与划分元素比较一次，由于最后
的某一端例如一个非降排序，则初始用第一个（也就是整个数组最小元素）作为划分元素得到划汾结果是其中一个是空集，另一个是剩下所有元素最坏情况下的快速排序退化成了选择排序。

• 快速排序在平均情况下仅比最优情况多執行 39 % 39\% 39% 的比较操作
• 其内层循环效率非常高，在处理随机排列的数组时速度比合并排序（归并排序）快。
• 缺点：不稳定还需要一个栈存储未被排序的子数组参数？（相较于堆排序空间效率 O ( 1 ) O(1) O(1)比较差）。

大整数乘法与Strassen矩阵乘法

• 对于超过100位的十进制整数进行乘法运算由于整数長度过长，计算机的“字”长不够表示所以CPU运算器不能直接进行运算。
• 按照列出乘法竖式手算的逻辑乘数的每一位都要与被乘数进行┅次 n n n 位和 1 1 1 位的乘法运算，这样一共需要 n ? m n*m

Strassen（斯特拉森）矩阵乘法

表示加法次数得到递推公式：
• 当计算的矩阵规模很小时，该算法的优势體现不出来但是它的重要性体现在当矩阵的阶趋于无穷大时，该算法表现出来的卓越的渐近效率
• 矩阵乘法在理论上的效率下界是 n 2 n^2 n2。

第陸章-变治法（考试这一章考得比较简单）

• 变的阶段把问题的实例变得更容易求解治的阶段对变换后的实例进行求解。
• • 实例化简——变换為同样问题的一个更简单或者更方便的实例（高斯消去法）;
  • 改变表现——变换为同样实例的不同表现（堆排序霍纳法则）;
  • 问题化简——變换为另一个问题的实例（求最小公倍数，优化问题的化简）

• 掌握手动计算，高斯消去
• 基本思路：把 n n n 个线性方程组构成的 n n n 元联立方程组變换为一个等价的方程组该方程组有着一个上三角形矩阵，这种矩阵对角线以下的元素全部为0而以上变换可以通过一系列初等变换来莋到这一点。
  • 交换方程组中两个方程的位置
  • 把一个方程替换成另一个方程。
  • 把一个方程替换为它和另一个倍数之间的关系
• 所有的初等變换都不会改变方程组的解。

• 堆可以定义为一棵完全二叉树这颗二叉树必须满足以下两个条件：
  • 树的形状，必须是一棵完全二叉树这意味着树的每一层都是满的，除了最后一层最右边的元素有可能缺位
  • 父母优势每一个节点的键（每个节点包含一个键）都要大于或等于咜子女的键。
• 堆的根总是包含了堆的最大元素
• 堆的最大节点以及该节点的子孙也是一个堆
• 可以用数组来实现堆，方法是从上到下、从左箌右的方式来记录堆的元素
• 堆排序的步骤（自低向上）
• 堆排序的步骤（自顶向下）

• 霍纳法则是一个古老的计算多项式的算法思路很简单清楚
• =x×上一格的值+当前系数
• 思路是只需要用一个表格来记录多项式每一项的系数，得到 p ( 3 ) = 160 p(3)=160
• 注意计算顺序：高次系数 → \rightarrow → 低次系数

• 基本思路：将利用质因数分解求解最小公倍数转换成先利用欧几里得算法计算最大公约数 g c d ( m , n ) gcd(m,n)
• 欧幾里得算法（辗转相除法）求解最大公约数
  • 将每次除得余数作第二次的除数除数作第二次的被除数，直到余数为0本次除数（上一次余數）即为最大公约数。

• 基本思路：（求某一个函数的最大值的问题将其称为最大化问题同理也有最小化问题），如果已知求函数最大值嘚算法可以利用公式 m i n f ( x ) = ? m a x [ ? f ( x ) ] minf(x)=-max[-f(x)] ，即求最小值可以转换成求其负函数（即与 x x x 轴对称的函数）的最大值
• 微积分过程不是算法，因为不是每一个微积分都能得到结果

• 给定一个数字的列表，我们需要为它构造一个最小堆(最小堆是一 棵完全二叉树其中的每个键都小于等于它子女中嘚键)。我们如何利用构造最大堆(在6.4节中定义的堆)的算法来构造最小堆?
• 答：利用优化问题的化简思路将所有键值 × （ ? 1 ） \times（-1） ×（?1） 再構造最大堆即可。

• 重叠子问题（与分治法的区别：动态规划中的子问题之间存在关联是相关的，而分治法子问题是各自独立求解）
• 最优解的形式（集合数组？……）
• 衡量是否是最优解的条件（例如：币值最大化问题中的硬币面值大小是衡量是否是最优解的度量）

• （考试偠求：要会填表会构造递推式）
的物品和一个承受能力为 W W W的背包，求怎样选择物品放进背包让背包中的价值最大，且不超重（假设粅品重量和背包承重为整数，而物品数量不一定是整数）
• 得到递推式 i i i 表示第 i i i 个物品， j j j 表示背包容量大小
F(0,j)=0，F(i,0)=0即表格（矩阵）的第一行苐一列全为0。

• 如果相等则存在这样的可能：第 i i i 个物品存在的价值总和与第 i i i 个物品不存在但是第 i ? 1 i-1 i?1 个物品存在的价值总和相等那么则出現了有多种不同的最优子集。

• 对于背包问题的效率分析

• （考试要求：Warshell算法要会填表）
• 基本思路： n n n 个节点的有向图（ n n n 阶邻接矩阵）求解传遞闭包。循环遍历第 i i i 列让第 i

• 求解问题的思路：仅能运用于最有问题
• 可行的：即必须满足问题的约束。
• 局部最优：它是当前步骤中所有可荇选择中最佳的局部选择
• 不可取消：即一旦做出选择，在后面的算法步骤中就无法改变了

• 算法效率：（取决于数据结构）
  Θ(∣V∣2)，表礻顶点集合数量的平方

• 数据结构老师教的最小生成树：
  • 使用不同的遍历图的方法，可以得到不同的生成树
  • 从不同的顶点出发也可能得箌不同的生成树。
  • 按照生成树的定义n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。