算法导论公开课笔记（一）算法分析与设计
算法分析
算法分析是关于计算机程序性能和资源利用的理论研究；性能研究主要是学习如何让算法或者应用程序 运行的更快； 资源利用主要指的是诸如通信、存储器（无论是RAM Memory还是disk Memory）等的使用情况。
算法是关注性能问题的学科，因此这部分内容很重要。
设想，如果你在一家公司从事软件开发工程的从事编程工作，有那些比性能更重要的东西？
- 代码简洁
- 可维护性
- 开发的时间成本
- 崩溃率
- 安全性
- 用户友好
佷明显，真实的软件开发场景中有诸多的方面都比性能重要。但是算法是关注性能的科学，如果算法和性能都不重要，我们为什么还要学习这样一个课程。
-
性能的好坏可以决定解决方案可行性。
-
算法是一种描述程序行为的语言，业已广泛应用于计算机科学领域，且已经被所有的实践者所采用的理论语言，它是思考程序最为简洁的一种方式。
性能为什么处于程序开发中的最底层。这里有一个很好的类比，性能在程序中扮演的角色就如同经济中的货币一样，货币可以购买人基本生活中所需的一切东西，如，食物，衣服，房子和水。可能水对你的生命而言比钱重要，但是你能买下这些商品的前提是有钱。同样，性能是确保良好用户体验的前提。 -
追求运行速度，是算法研究最让人兴奋的地方。
排序问题
通过排序问题，进行算法分析。
插入排序
插入排序的伪代码如下：
INSERTION-SORT(A)
1 for j=2 to A.length
2 key=A[j]
3 //将A[j]插入到有序的子数组A[1..j-1]。
4 i=j-1
5 while i>0 and A[i]>key
6 A[i+1]=A[i]
7 i=i-1
8 A[i+1]=key
Java 版本代码实现如下：
void insertSort(int[] arr){
if(arr==null||arr.length<2) return;
for(int i=1;i<arr.length;i++){
int key=arr[i];
int j=i-1;
while (j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
运行时间分析
运行时间依赖于下面的因素
- 输入项
- 输入项的规模
分析运行时间的方式
- 最坏情况-Worst-case（usually）
T(n) = max time on any input of size n - 平均情况-Average-Case（somtimes）
T(n) =excepted time all input size n
前提是，需要一个有关输入统计分布的假设
每种输入的运行时间乘以该输入出现的概率进行加权平均所得到的时间，就是期望运行时间 - 最好情况Best_Case（假象）
假设，用已经做好排序的序列检验"低速"算法，得到的运行时间可以的到最好情况。
最坏情况的运行时间分析：
- 依赖使用的计算机、
相对运行时间（在相同计算机上运行）
绝对运行时间（在不同计算机上运行）
渐进分析（Asymptotic Analysis）
- 忽略那些依赖于机器的常量
- 当n趋近于∞过程中，忽略机器实际的运行时间，而是T(n)的增长
渐进符号
- Θ 标记
渐进紧确界
舍弃低阶项，并忽略前面的常数因子
例如，如果公式为3n³+90n²-5n+6046=Θ（n³）
当n->∞时Θ（n²）的算法总是能战胜一个Θ（n³）的算法，其他项不会动摇这个结果，假设在一台性能好的机器上运行Θ（n³）的算法，在一台性能差的机器上运行Θ（n²）的算法，只要n足够大，Θ（n²）的算法总是能战胜一个Θ（n³）的算法，这个结论依然成立，这就是渐进符号的伟大之处（它能一举满足我们对相对和绝对速度的双重比较要求）。
image.png
从工程视角来看有时临界值n0的过大，大到计算机无法运行，这就是我们为什么会对低速的算法馆兴趣的原因，有一些算法尽管用渐进的观点来看，他们有可能比较慢，但是在合理规模输入的情况下运行的更快，所以我们要从数学的理解和工程的直觉之间寻找平衡，这样我们才能写出更好的程序。仅仅会做算法分析，并不能是你成为一个编程高手。
老司机讲段子，“如果你想成为编程高手，你可以在两年中每天编程；如果你想成为世界级的编程高手，你可以每天编程，然后上一门算法课”。
插入排序的算法分析
内存引用计数。
最坏情况：T（n）=
image.png
-
O 标记
Θ 标记渐进的给出了一个函数的上界和下界，当只有一个渐进上界时，使用O 记号。 -
Ω 标记
正如O标记提供了一个函数的渐近上界，Ω 记号提供了渐近下界。
算法设计
我们可以选择使用的算法设计技术有很多。插入排序使用了增量方法：在排序子数组A[1..j-1]后，将单个元素A[j] 插入子数组的适当位置，产生排序好的子数组A[1..j]。
下面考查一种“分治法”的设计方法，我们将用分治法来设计一种排序算法，该算法的最坏情况的运行时间比插入排序要少得多。分钟算法的优点之一是，通过算法分析技术很容易确定其运行时间。
分治法
早在中国汉代就有使用。中国历史版本"分治法"之推恩令。
推恩令是汉武帝为了巩固中央集权而颁布的一项重要政令。这项政令要求诸侯王将自己的封地分给自己的子弟。后来根据这项政令，诸侯国被越分越小，汉武帝再趁机削弱其势力。
许多算法结构上的递归的：为了解决一个给定的问题，算法一次或多次的递归调用其自身以解决相关的若干子问题。将原问题分解为几个规模较小但是类似原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时的三个步骤：
- 分解
- 解决
- 合并
归并排序
- 分解
分解待排序的n个元素的序列成n/2个元素的两个子序列。 - 解决
使用归并排序递归的排序两个子序列。 - 合并
合并两个已经排序的的子序列以产生一排序的答案。
插入排序的伪代码如下：
MERGE-SORT(A)
1 for j=2 to A.length
2 key=A[j]
3 //将A[j]插入到有序的子数组A[1..j-1]。
4 i=j-1
5 while i>0 and A[i]>key
6 A[i+1]=A[i]
7 i=i-1
8 A[i+1]=key
Java 版本代码实现如下：
/**
* 前提[l,mid]有序并且(mid,r]有序 目标：通过
*
* @param src
* i:{6,9,10,2,8,11} out:[2,6,8,9,10,11]
* @param tmp
* 临时存放顺序的数组
* @param left
* @param mid
* @param right
*/
public static void mergeArray(int[] src, int[] tmp, int left, int mid,
int right) {
int tmpIndex = left;
int leftStart = left;
int rightStart = mid + 1;
while (tmpIndex <= right) {// 临时数组为填满表明合并未完成
if (leftStart <= mid && rightStart <= right) {// 这种情况是两个subarray都未合并结束
tmp[tmpIndex++] = src[leftStart] < src[rightStart] ? src[leftStart++]
: src[rightStart++];// 条件成立者赋值给临时数组后索引右移（+1）
} else if (leftStart <= mid) {// 这种情况证明右侧的subArray合并结束
tmp[tmpIndex++] = src[leftStart++];
} else if (rightStart <= right) {// 这种情况表明左侧的subArray合并结束
tmp[tmpIndex++] = src[rightStart++];
}
}// 临时数组保存了 [left,right]的合并结果
System.arraycopy(tmp, left, src, left, right - left + 1);
}
/**
* 二路归并实现
* @param src
* @param tmp
* @param left
* @param right
*/
public static void mergeSort(int[] src, int[] tmp, int left, int right) {
if (left >= right)
return;
int mid = (right + left) / 2;
mergeSort(src, tmp, left, mid);
mergeSort(src, tmp, mid + 1, right);
mergeArray(src, tmp, left, mid, right);
}
归并排序的时间复杂度为 Θ（nlgn），随着规模n的增大，归并排序的运行时间达到了渐进最优，但是归并排序的一个缺点是需要开辟一个同等长度的内存空间才能正常运行。
以上，谢谢阅读，希望你有所收获！
算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法
