算法课

插入排序

伪代码

    for j = 2 in 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

ipad上有示意图帮助理解

运行时间

输入是否有序
input size
upper bound

分析的类型

Worst case(usually)
T(n) = max time
Average case
T(n) = expected time(一般这种情况需要输入的分布)
Best case
bogus，这种情况几乎不存在，教授戏称假象

使用渐进分析判断最糟糕的情况

渐进分析

忽略机器因素
关注增长

$\theta$ -符号

弃去低阶项，忽略常数因子。(有时候 $\theta(n^3)$ 比 $\theta(n^2)$ 好，在n相当小的情况下，可看ipad上示意图)

插入排序分析

逆序时情况最糟
$T(n)=\sum_{j=2}^n{\theta(j)=\theta(n^2)} (算术级数,Arithmetic series)$

归并排序

T(n)	Mergesort A[1...n]
$\theta(1)$	1.If n=1, done
2 $T(n/2)$	2.Recursively solve A[1, [n/2]] and A[[n/2]+1, n]
$\theta(n)$	3.Merge two sorted lists

$T(n) = 2T(n/2) + cn \qquad c>0$
T(n)可以用递归树方法或主方法解出来。
将在2019_4_1中提到

随笔2019-03-29