由于我上了算法分析这门课，希望能稍微整理一下所学，于是我分享我的笔记在这。下面是一些总结。
- Insertion sort, efficient algorithms
- Analysis of algorithms
- Insertion sort
- Efficient algorithms
- Asymptotic notation, margesort, recurrences
- Asymptotic notation
- Divide and conquer: merge sort
- Asymptotic notation, margesort, recurrences
- Efficient algorithms
Insertion sort, efficient algorithms
Analysis of algorithms
正确性 correctness：一般用数学归纳法。claim，base case，induction hypothesis，inductive step，conclusion。
时间 running time：初始步骤的数量；我们注意不是运行时间不考虑硬件，我们想知道运行时间如何随输入的规模变化。best case，worst case，average case。
空间 space：多少额外空间解题。
Insertion sort
想法？
把unsorted列表变成sorted列表，也就是找到边界点在sorted列表的正确位置。
过程？
排序从1位置到n位置的数字，遍历i从2到n；i位置之前的是排好序的sorted范围（因为i=1的时候列表已经排好序了，所以直接从2开始遍历i），包括i及以后的部分是unsorted范围；我们把i位置的数字存到变量key里面，遍历j<i位置的数字；如果j位置的数字大于i位置的数字，则j位置的数字挪到j+1位置（因为i位置已经放到key变量里面了，不担心覆盖问题），直到j位置的数字小于等于i位置的数字，我们停下，让j+1位置的数字为key变量存的值（因为key变量存的是最初的A[i]）；当i遍历完成后，就排好序了。
调用？
insertion-sort(A)；输入是arrayA，输出是排好序的A。
正确性？
在i-th循环后，A[1,i]是排好序的。证明略。
时间？
O(n^2)
空间？
in-place
Efficient algorithms
An algorithm is efficient if it has a polynomial running time. 有多项式运行时间的都是efficient的。
Asymptotic notation, margesort, recurrences
Asymptotic notation
Big O：asymptotic upper bounds 渐进上界。
Big Omega：asymptotic lower bounds 渐进下界。
theta：asymptotic tight bounds 渐进界。
little o：asymptotic upper bounds that are not tight。
little omega：asymptotic lower bounds that are not tight。
Divide and conquer: merge sort
想法？
一个array可以分成两个相等大小的array，分别排好序，再排序整个大的。
过程？
mergesort(A, left, right) 如果left==right返回；不然就：计算mid，mergesort(A, left, mid)，mergesort(A, mid+1, right)，merge(A, left, right, mid)。
merge(A, left, right, mid) 复制值得到arrayL和R，使用两个指针pl和pr，如果L和R都不是空的，则比较 L[pl] 和 R[pr] 值，小的放入A；最后把剩下的L或者R的全部值都放入A的结尾。
调用？
mergesort(A, left, right)，调用 mergesort(A, 1, n)；merge(A, left, right, mid)，
正确性？
2^k大小的可以排序，则2^(k+1)大小的也可以排序。证明略。
时间？
T(n) = 2T(n/2)+cn ⇒ O(nlogn)
空间？
theta(n)
Asymptotic notation, margesort, recurrences
Efficient algorithms
想法？
过程？
调用？
insertion-sort(A)；输入是arrayA，输出是排好序的A。
正确性？
在i-th循环后，A[1,i]是排好序的。证明略。
时间？
O(n^2)
空间？
in-place