本系列文章是我学习算法概论(第三版)这本书的一些笔记和感悟，我没有纯看书，而是结合了MIT的公开课，把书籍作为课本，查看具体细节，主要是看课程，每节课时长60分钟左右，视频在网易公开课上有中文字母。次课程会从数学的角度去分析运行时，课程总共有21，前6课讲解都是排序算法，对应课本上的前三章，这部分不涉及到数据结构,后面的章节都涉及数据结构以及应用。

算法分析

为什么学习算法和性能

• 算法帮助我们去理解可扩展性。
• 性能常常用来划分什么是可行的什么是不可行的。
• 算法数学提供了一个讨论程序特性的语言。(用数学来刻画程序的特性，比如运行时)。
• 性能是计算机的共性。
• 程序性能和计算机资源是无关的。比如一台很老的电脑和一台现代的电脑相比，不能说现代电脑就一定比旧电脑运行的快，如果旧电脑运行的算法比较高效的话，一定会在某一时刻运行时间会小于新电脑。

排序问题

Input: 一个序列 <a1,a2,a3,.....,an> Output: 输出一个排序后的序列<a1',a2',a3',......,an'>, 使得 a1' < a2' < a3' < .... < an'

插入排序

伪代码

Insertion-SORT(A,n)
    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

func InsertionSort(A []int)  {
	for i:= 1; i < len(A) ; i++  {
		key := A[i]
		j := i-1
		for ; j >=0 && A[j] > key ; {
			A[j+1] = A[j]
			j = j-1
		}
		A[j+1] = key
	}
}

运行时分析

• 运行时依赖输入，如果输入是排好序的，那是很容易排序的。
• 输入元素的个数，短序列比长序列更好排序。
• 通常来说，我们分析的是运行时的上限。

分析的方式

• 最差情况(通常用次分析)

T(n) = 算法的最长运行时在任何的输入下。

• 平均情况

T(n) = 算法的预期时间在总体输入下。

• 最好情况

T(n) = 在某些输入下运行时间比较好。

插入排序分析

$$ T(n)=\sum_{j=2}^{n} \Theta(j)=\Theta\left(n^{2}\right) $$

我们分析最差情况，如果输入是逆序的，那么执行的次数就是n+(n-1)+(n-2)+...+1=n(n-1)/2 就是一个等差数列求和，就得到如上的公式，

$$ T(n)=\Theta\left(n^{2}/2\right) + \Theta\left(n-1\right) $$

忽略低阶项和高价项的常数，就得到如下运行时间，所以插入排序是和输入大小成平方比。

$$ T(n) = \Theta\left(n^{2}\right) $$

归并排序

伪代码

# MERGE-SORT(A)
    1. Ifn=1,done.
    2. 递归排序 A[ 1 . . ⎡n/2⎤ ] and A[ ⎡n/2⎤+1 . . n ] . # ⎡n/2⎤ 向下取整
    3. 合并这两个`list`

归并排序分析

这个公式在后面会用主方法来进行分析运行的上界。

递归树的高度是lgn，每一个层级运行时为cn，所以Tn = O(cn*lgn),就是高度乘以每一层的时间，前面的c为常量，可以忽略。

结论

• Θ(nlgn)比Θ(n2)慢的多。
• 归并排序在最坏情况下比插入排序好的多。
• 实践中，当n > 30 时，归并排序就比插入排序好的多。