2018-02-19算法导论课程笔记（插入，归并，代换，递归树，

性能就好像是平常的货币一样，我们用它交换安全和性能。

Insert—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

Insert—Sort（A，n） 图解

插入排序原理

asymptotic analysis(渐近分析)

一般分析分为最坏情况分析（worst-case）、平均时间分析（average-case）、 最好情况分析（best-case）一般情况下我们认为best-case是无用的（bogus），大多是情况下我们都是分析worst-case，这种情况决定了他的上界（upper-bound），我们设这种情况为T（n）

θ：drop low order terms and ignore leading constant(舍弃低阶项和忽略高阶项系数)

对insert-sort T（n）分析：
T（n） = ∑（j=2 ->n）
θ(j) = θ(n²) 因为由上面的公式可知，其为等差数列的累加过程，是算术级数（Arithmetic series）

T（n）	Mere—Sort
θ（1）	1.If n=1 ，done
2T（n/2）	2.递归排序 A:[1-n/2] and A:[n/2-n]
θ（n）	Merge 2 sorted list

归并排序

T（n） = 2T（n/2）+ Cn

递归树

初识递归树

O(O-notation) means <=
ω(omega-notation) means >=
θ = O() ∩ ω()

代换法

1. 猜测问题的答案
2. 按照数学归纳法满足条件
3. 找出系数，解决问题

Example

T（n） = 4T（n/4） + n
Guess T（n） = O（n³）
T（k） <= ck³

T（n） =  4T（n/2） +  n
       ≤ 4(n/2)³ + n
       = 1/2cn³ + n
       = cn³ -（1/2cn³-n）

在c≥1 and n≥1 的情况下（1/2cn³-n）恒大于0
所以假设成立T（n） = O（n³）

递归树法（之前出现的归并算法中已经用到）

Example

定理4.1（主定理） 令 a≥1 和 b>1 是常数，f(n) 是一个函数，T(n) 是定义在非负整数上的递归式：
T(n) = aT(n/b) + f(n)
那么T(n)有如下渐进界：
1.若对某个常数 ε>0 有 f(n) = O(nlogba-ε)，则 T(n) = Θ(nlogba) 。
2.若 f(n) = Θ(nlogba)，则 T(n) = Θ(nlogba lgn) 。
3.若对某个常数 ε>0 有 f(n) = Ω(nlogba+ε)，且对某个常数 c<1 和所有足够大的 n 有 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n)) 。

案例1：

T(n) = 9T(n/3) + n
对于这个递归式，我们有 a = 9，b = 3， f(n) = n，因此 nlogba = nlog39 = Θ(n2) 。而 f(n) = n 渐进小于 Θ(n2)，所以可以应用于主定理的情况1，从而得到解 T(n) = Θ(n2) 。

案例2：

T(n) = T(2n/3) + 1
其中，a = 1， b = 3/2， f(n) = 1，因此 nlogba = nlog3/21 = n0 = 1 。由于 f(n) = Θ(1) ，与Θ(nlogba)恰好相等，可应用于情况2，从而得到解 T(n) = Θ(lgn) 。

案例3：

T(n) = 3T(n/4) + nlgn
我们有 a = 3，b = 4，f(n) = nlgn，因此nlogba = nlog43 = O(n0.793) 。由于 f(n) = Θ(nlgn) = Ω(n2) = Ω(n0.793+1.207)，因此可以考虑应用于情况3，其中 ε = 1.207。但需要检查是否满足条件：当 n 足够大时，存在 c<1 使 af(n/b) ≤ cf(n) 。
令 3f(n/4) ≤ cf(n) 有
3n/4lg(n/4) ≤ cnlgn
3/4(lgn - lg4) ≤ clgn
(3/4 - c)lgn ≤ 3/4lg4
容易发现，当 c ≥ 3/4 时，上式对于足够大的 n 恒成立。因此可以使用主定理的情况3，得出递归式的解为 T(n) = Θ(nlgn) 。

分治法

1.Divide
2.Conquer
3.combine

Binary search

1.Divide:把X与数组的中间元素相比较
2.Conquer:数组大小变为原来的一半
3.combine:无
T（n） = T（n/2）+ θ（1）

乘方问题&Fibonacci

乘方&Fibonacci

strassen矩阵算法

strassen

VLSI

VLSI是超大规模集成电路(Very Large Scale Integration)的简称，指几毫米见方的硅片上集成上万至百万晶体管、线宽在1微米以下的集成电路。

VLSI Layout

Naive Algorithm

VLSI layout - naive

Quick Algorithm

Quick Algorithm

Quick-Sort

快速排序的特点
-Divide and conquer
-Sorts in place
-Very practical

基本思路 例子

j向右边移动，如果遇到比6大的数字则继续像右移动，如果遇到比6小的数字，将该数字与i+1下标数组数字交换，最后交换a[i]和一开始的参照数。

快排算法时间分析（worst-case ：每次分出来的两边数组都是1个元素和n-1个元素）

worst

快排算法其他情况下的分析

1.将数组正好对半分（best-case）
2.将数组分为1/9开（或者其他开）
3.最好情况和最坏情况交替出现
以上情况最终结果都趋向于θ（nlogn）
因此快排有最适合于实际运用的特点

证明推导如图

Best-case证明 1-9开case证明 好坏交替case证明