MIT 算法导论(1) - 算法分析，学习记录
算法导论，是MIT非常经典的一门算法课程，之前也买过（CLRS）来看，但是一直没有坚持看完，里面有很多数学证明非常饶头 :(
这次找来视频，准备好好学习一遍。
1. MIT’s Introduction to Algorithms, Lectures 1 and 2: Analysis of Algorithms
首堂课的核心是算法分析，然而算法分析到底是什么？
算法分析 就是关于计算机性能和资源使用的理论研究
“Analysis of algorithms is the theoretical study of computer program performance and resource usage”.
第一讲给我的感觉就是，你真的需要记笔记，不懂的地方需要来回多看几次视频，主讲老师本身就是《算法导论》的作者，几乎句句经典没什么废话。
一上来就是切入主题，讲如何分析算法，并详述了渐进分析思路，被他成为：Big Idea，该分析方法的思想主要集中在如下几点：
- 首先忽略掉那些依赖机器的常量；
- 以及，不去检查算法实际运行时间，而是关注运行时间的增长；
T(n), n -> ∞，也即，当 n 趋近于无穷大时，运行时间 T(n) 的增长（或者说，如何变化，比如有些算法突破某个点时，耗费时间是急剧增加，有些则是缓慢增长）
算法的选择实际上很多时候是依据具体情况做权衡，某些看上去很慢的算法，在数据量较小的时候，也许优于其他看似快速的算法。因为某些算法必需突破某个点时，才能显现其速度优势，但是这个点的规模也许已经大到计算机无法运行的地步，因此我们有时会对一些相对低速的算法感兴趣。
接下来，Charles E. Leiserson 教授采用渐进法，对插入排序（Insertion Sort）和 归并排序（Merge Sort）进行了完整的时间复杂度分析。具体分析过程大家可以看视频，我主要想说自己的几点感想：
- 数学证明在算法分析上面确实可行，理解它对于帮助我们理解算法确实有很大帮助；
- 伪代码确实可以帮助我们了解算法的理论，并且可以在一定程度指导我们如何编写实际的代码；
- 理解算法的原理和是否能够写出算法的实现，真的是两码事，重要的事，我不想再说很多遍，这个真的不一样；你可以设计一个算法，你可以用数学不等式证明你算法的有效性，但是你不一定能够用一种语言正确的实现该算法。具体到代码层面，真的和工程实践有关，你必须不断练习，才能写出正确无误的代码。因此，当你上完课，仍然无法实现该算法的时候，不要灰心，我猜很多人都是如此。满脑理论，一写就废，不在少数。 据统计，去谷歌面试的工程师，能够现场写出正确无误的二分查找算法的人，连一半都没有 ：）
最后，附上我用Golang实现 Insertion Sort 和 Merge Sort 的代码：
//Chapter 2.1, insertion sort, implement it by golang
//Author: Raymond Jiang
//Date: 2019-06-20
//Insertion Sort O(n*n)
func InsertionSort(arrs []int) {
for i := 1; i < len(arrs); i++ {
key := arrs[i]
j := i - 1
for j >= 0 && arrs[j] > key {
arrs[j+1] = arrs[j]
j--
}
arrs[j+1] = key
}
} //Chapter 2.3, merge sort, implement it by golang
//Author: Raymond Jiang
//Date: 2019-06-25
//Merge sort O(n*lgn)
func MergeSort(arrs []int, p, r int) {
if p < r-1 {
q := (p + r) / 2
MergeSort(arrs, p, q)
MergeSort(arrs, q, r)
Merge(arrs, p, q, r)
}
}
func Merge(arrs []int, p, q, r int) {
left := make([]int, q-p)
copy(left, arrs[p:q])
right := make([]int, r-q)
copy(right, arrs[q:r])
j := 0
i := 0
for k := p; k < r; k++ {
if i == len(left) && j < len(right) {
arrs[k] = right[j]
j++
continue
}
if j == len(right) && i < len(left) {
arrs[k] = left[i]
i++
continue
}
if left[i] < right[j] {
arrs[k] = left[i]
i++
} else {
arrs[k] = right[j]
j++
}
}
}