性能就好像是平常的货币一样，我们用它交换安全和性能。
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() ∩ ω()
代换法
- 猜测问题的答案
- 按照数学归纳法满足条件
- 找出系数，解决问题
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证明
网友评论