算法设计与分析基础

第一章：绪论、

欧几里得算法：

证明：等式 gcd(m,n)=gcd(n, m mod n) 对于每一对正整数（n,m）都成立

我一天说着复习，但是突然打开了沙雕电视剧，突然发现了这下我也没有好好的学习，哎呀，这些天简直了，我们 也要这样好好的学习，狭路相逢勇者胜

渐进符号和基本效率类型：

三个符号

非递归算法的数学分析：

分析非递归算法效率的通用方案

1 决定用哪个（哪些）参数表示输入规模。

2 找出算法的基本操作（作为一个规律，它总是位于算法的最内层循环中）。

3 检查基本操作的执行次数是否只依赖于输入规模。如果它还依赖于一些其他的特性，则最差效率，平均效率以及最有效率需要分别研究。

4 建立一个算法基本操作执行次数的求和表达式。

5 利用求和运算的标准公式和法则来建立一个操作的闭合公式，或者至少确定的增长次数。

分析递归算法时间效率的通过方案

1 决定找出那个（哪些）参数作为输入规模的度量标准。

2 找出算法的基本操作

3 检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这种可能，则必须对最差效率，平均效率以及最优效率做单独研究。

4 对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。

5 解这个递推式，或者至少确定它的解的增长次数。

突出主题：

计算第N个斐波拉契数列：

算法的经验分析：

1 了解实验的目的

2决定用来度量效率的度量标准M和度量单位（是操作次数还是操作时间）

3 决定输入样本的特征（它的范围和大小等

4 为实验准备算法（或者若干算法），并记录观察到的实验数据

5 生成输入样本

6 对输入样本运行算法（或者若干算法），并记录到观察到的实验数据

7 分析获得的实验数据。

蛮力法：是一种简单直接地解决问题的方法，常常直接基于问题的描述和所设计的概念定义

选择排序：    我们扫描整个列表，找到它的最小元素，然后和开始第一个元素交换，将最小元素放在他在有序表中的最终位置上。然后我们把第二个元素开始扫描列表，找到第n-1个小的元素，放在第二个位置上，把第二个元素放在它的最终位置上。是一个时间复杂度在n
的平方

冒泡排序：它比较与它相邻的；两个元素之间的大小，交换他们之间的位置，它的时间复杂度也是N的平方

循序查找和蛮力法字符串匹配：

顺序查找：简单地将给定列表=中连续和给定的查找键盘进行比较（失败查找），知道遇到第一个匹配的元素（成功查找），或者在遇到匹配元素前就遍历了整个列表

蛮力法字符串匹配：

给定一个由N个字符组成的串，一个由M个字符组成的串，从文本中寻找匹配模式的自串

穷举查找：他要求生成问题域中的每一个元素，选出其中满足问题约束的元素，然后再找出一个期望元素（例如：是目标元素达到最优的元素）

旅行商问题 哈密顿回路  找出N个城市之间的最短路径，每个城市只走一遍

背包问题  把最有价值的赃物放进小偷的背包
每个物品有不同的价值和重量，而小偷只能带走一定质量的物品，怎么做到带走的价值最高 算法复杂度为欧米伽2的N次方的算法复杂度

分配问题：就是N个人有N个任务，每个人完成每个任务的时间不同，但是每个人只能完成一件任务，怎样分配才能所用的时间最短
时间复杂度为N的阶乘

深度优先查找：可以从任何顶点开始访问图的顶点，然后把

该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点临接的未访问的顶点
从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

DFS深度优先查找比较容易找到解，但不一定是最优解，但是它占的内存小，适合深度大的

而BFS广度优先查找会找到最优解

减治法：

减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的关系，一旦建立这种关系我们就可以自顶向下，也可以从底向上地来运用该关系

三种主要的变化形式

减去一个常量  ：每次算法迭代总是从实例中减去一个相同的常量

减去一个常量因子 ：每次算法迭代中从实例的规模中减去一个相同的常量因子

减去的规模是可变的： 算法在每次迭代的时候，规模减小的模式都是不同的

插入排序： 我们从左到右扫描这个有序的子数组，直到遇到第一个小于等于它的元素，然后把它插入到该元素的后面  最好的时间算法复杂度： N  最坏和平均的算法复杂度： N的平方

拓扑排序：

邻接矩阵和邻接链表依然是表现有线图的主要手段：

生成排序：

生成子集

减常因子算法

折半查找：

假币问题 俄式乘法 约瑟夫斯问题

减可变规模算法

插值查找 二叉树的查找和插入
 拈游戏

分治法：

1讲一个问题划分成同一类型的若干子问题，子问题最好规模相同

2 对这些子问题求解（一般选择递归方法，但在问题规模足够小的时候，有时也会利用另外一个算法）

3有必要的话，合并这些问题的解，已得到原始问题的解

合并排序

快速排序

二叉树遍历及其相关特性

大整数乘法和Strassen 矩阵乘法

变治法：

1变换为同样问题的一个更简单或者更方便的实例，我们称之为实例化简

2变化为同样实例的不同表现 我们称之为改变实现

3变换为另一个问题，这种问题的算法是我们已知的，我们称之为问题化简

预排序

高斯消去法;

计算矩阵的逆 计算矩阵的行列式
  平衡查找树
   AVL树    堆和堆排序

堆的排序：

树的形状：这棵二叉树基本完备，这意味着树的每一层都是满的，除了最后一层最右的元素可能为空

父母优势：每一个节点的键都要大于或者等于它子女的键

霍纳法则和二进制幂