麻省理工学院公开课：算法导论。B站地址，网易公开课也有对应的资源。
https://www.bilibili.com/video/av1149902/
本节课的主要内容是，课程准备和插入排序、归并排序的算法分析。
课程准备（讲了约17分钟）
预备知识：离散数学、概率论。都是大学计算机专业的必修课程。
考勤之类的：不能缺勤，要按时按成习题集之类的。
算法分析是理论研究，关于计算机程序性能和资源利用的研究。计算机资源，包括通信、存储器、内存、磁盘存储等。
这是一门关注性能的课程。对于程序员来说，有很多比性能重要的东西。如安全性、正确、简洁、可维护性、健壮性、可扩展、用户友好、功能性、模块化等等。但是性能也非常重要，对于实时应用，如果性能不好，影响了实时性，那就失去了实时的功能。对于占用大量内存的应用，如果性能不好，也是会直接崩溃无法使用的。
排序问题
关于排序问题的算法有很多种。课程中讲了两种：插入排序、归并排序
插入排序
伪代码如下：（数组为A[]）
for j <- 2 to n
do key <- A[j]
i <- j-1
while i>0 and A[i]>key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key
用JavaScript语言描述如下：
var key;
for(var i=1;i<n;i++){
key = A[i]; //保存当前项为常量key
for(var j=i-1;j>=0;j--){ //遍历当前项前面的值，找到合适的位置插入
if(A[j] > key){
A[j+1] = A[j];
}
}
A[j+1] = key; //找到当前项合适的位置，插入
}
现在对以上算法进行分析，从三个方面进行：最坏的情况（全部逆序），平均情况（涉及到概率论相关知识，每种输入的情况对应的概率），最好的情况（全部正序）。
运用渐近分析。
渐近分析：忽略依赖于机器的常量，不检查实际的运行时间，而是关注运行时间的增长。
渐近符号之一——θ符号（这门课程中常用的符号）：弃去低阶项，忽略常数因子。θ是一个弱符号，是一个描述符号，而不是运算符号。
例如：
3n^3+90n^2-5n+6046
可以表示为θ(n^3)
最坏的情况，就是数组中的数字都是倒序，这种情况下的时间消耗为θ(n^2)。
归并排序
一个思路，没有列出具体的代码
- if n=1，done. 时间复杂度为θ(1)
- 将数组A分成两个数组，分别是[a1,a2,...,a(n/2)],[a(n/2+1),...an]，分别对其进行排序，时间复杂度为2T(n/2)。T(n)表示对一个长度为n的数组进行排序所需要的时间复杂度。
- 将两个排好序的数组进行合并。对比两个数组的第一个元素，将小的那个push进新的数组内，然后继续对比。时间复杂度为θ(n)。
时间复杂度T(n)有两种情况：
1、if n=1, T(n) = θ(1)
2、if n>1, T(n) = 2T(n/2)+θ(n)
T(n) = 2T(n/2)+cn（n是大于0的常数）
下面使用递归树的方法来对T(n)进行分析：
T(n) = 2T(n/2)+cn
= 4T(n/4)+cn+2c(n/2)
= 8T(n/8)+cn+2c(n/2)+4c(n/4)
= nT(1)+cn+cn+cn+...+cn
= nT(1) + cn*lgn
= θ(n)+θ(nlgn)
= θ(nlgn)
每次都将数组一分为二，直到最后T(1)=θ(1)（理想情况下，假设n为2的指数倍），一共需要进行lgn次分解，每次都会分解出一个cn，共lgn次，故为cnlgn，忽略常量，即为nlgn。
分析结果其时间复杂度为θ(nlgn)。
也就是：
1、if n=1, T(n) = θ(1)
2、if n>1, T(n) = 2T(n/2)+θ(n) = θ(nlgn)
在n比较大的情况下，优于插入排序算法。
网友评论