this is the summary that I watch from tudou , It's deeply impressed me.I get a lot from it.
here is my summary share with you.the two lesson talked about two lessons with <divide and conquer algorithm>. this impressed me alot.
the second lesson talk about :
first how to calculate the steps with divide and conquer algorithm there are three methods 1 sabstitation 2recursion-tree-method 3 master method:
second the meaning of each mathmatic signs.
the third lesson talk about:
several examples on divide and conquer algorithm. 1 powering a number .2 binary search 3.fibonacci 4 matrix multiplication (strassen algorithm)
second lesson:
talk about the three sign θ Ω Ο
θ in this video , the professor talked about the sign θ is this function. drop leading low order terms,lead constant and ignore leading constant.and we usually use θ() to describe a problem .like we usually describe the merge sort with θ(nlgn).
for example .the steps is 3n3 + n2 +3. and the θ (n3 ) {drop leading low order terms,lead constant and ignore leading constant}
Ω we use f(n)=Ω(g(n)) this is the above bound . and θ is talk about the below bound.
0<=c g(n)<=f(n) c is constant.
0<f(n)<=c g(n) ------------------------ review this things. to know better.
1 sabstitation 1 guess from exaclly
2 figure the constant
3 solve the constant (verfiy the recurrence)
for example T(n)=4T(n/2)+n
guess:Tn=O(n3)
assume : Tk =ck3
T(n)=4c(n/2)3+n=1/2cn3 +n=cn3-(1/2cn3-n) to prove it no bigger than cn3
{(1/2cn3-n)}is the residuals.
to prove it bigger than zero. only c>=2;
guess:Tn=O(n2)
assume : Tk =ck2 is not right.
let us to guess
guess:Tn=O(n2)
assume : Tk =c1k2 -c2k is not right.
T(n)=4T(n/2)+n
=4(c1(n/2)2-c2*n/2)+n
=c1n2-c2n-(-1+c2)n c2>=1; It is said that c1 is much larger than c2. from basic examples.
2 recursion tree : this is nonrigorous and we use is a sloppy way.
let's to solve a more complicated recursion.
draw a recursion tree
n2 sum up n2
(n/4)2 (n/2)2 sum up 5/16n2
(n/16)2 (n/8)2 (n/8) 2 (n/4)2 sum up 25/256n2
sum up each lines time cost.
this is geometric numers. sum them up. you can use this as an example 1+1/2+1/4+1/8+----=2
this geometric ultimiate answer is 2.
so the sum is less than 2n2. and the answer is θ (n2).
here is the key method .
3 master method :
this method is only apply to particular family of recursion.
T(n)=aT(n/b)+f(n) f(n)is non-recursion work.
case 1: f(n)=Θ(n lga/lgb-ε) ε>0
Tn= θ (nlga/lgb) small
case 2: f(n)=Θ(nlga/lgb*lgkn)
T(n)=Θ(nlga/lgb*lgk+1n) equal
case 3: f(n)=Ω ( n lga/lgb+ε) large
af(n/b)<=(1-ε')f(n)
Tn=Θ(f(n))
T(n)=4T(n/2)+n nlga/lgb=n2 suit to case one the answer is Θ(n2)
T(n)=4T(n/2)+n2 n2 = n2 the answer is Θ(n2logn);
T(n)=4T(n/2)+n3 the answer is Θ(n3);
the third lesson is divide and conquer
1 powering a numer is easy the common method is Θ(n);
the improved method is Θ(lg n);
2 binary search is also easy the answer is Θ(lg n);
3 fibonacci can be used by recursion ,but it cost a lot of time and space to finish it . it 's Exponential time.
and we can use matrix multiplication to calculate it.
we use [1,1;1,0];to calculate it.
it reprsent [fn-1,fn-2;fn-2,fn-3].
[fn,fn-1;fn-1,fn-2]= [fn-1,fn-2;fn-2,fn-3]*[1,1;1,0];
this is the right answer. Θ(lg n)
remember it can not change the position of two matrix
like a*b!=b*a
but to this problem it is right ,because a=b.this is an exception.
4 the matrix multiplication (strassen algorithm)
pseudocode i 1~n
j 1~n
cij=0
k 1~n
cij+=aik*bkj
this is Θ(n3)
and we can use strassen algorithm.
is Θ(nlg7);
you need to complete the matrix as the power of 2. is there are not a matrix as the power of 2,add zero in it.
and use this steps.
1969年斯特拉森利用分治策略并加上一些处理技巧设计出一种矩阵乘法。
为了得到2矩阵相乘的分治算法1、定义一个小问题，并指明那个问题如何进行乘法运算，2、确定一个大问题，进行划分，如何指明对这些小问题进行乘法运行。
设A和B是俩个n x n的矩阵，其中n可以写成2的幂。将A和B分别等分成4个小矩阵，此时如果把A和B都当成2x2矩阵来看,每个元素就是一个（n/2）x（n/2）矩阵，而A和B的成积就可以写成〔A11 A12〕[B11 B12] [C11 C12]
X =
[A21 A22] [B21 B22 ] [C21 C22]
其中 利用斯特拉森方法得到7个小矩阵，分别定义为：
m1=(A12=A22)(B21+B22)
m2=(A11+A22)(B11+B22)
m3=(A11-A21)(B11+B12)
M4=(A11+A12)B22
M5=A11(B12-B22)
M6=A22(B21-B11)
M7=(A21+A22)B11
矩阵m1~m7可以通过7次矩阵乘法、6次矩阵加法和4次矩阵减法计算得出，前述4个小矩阵可以由矩阵m1~m7，通过6次矩阵加法和2次矩阵减法得出，方法如下：
c11=m6+m1+m2-m4
c12=m5+m4
c21=m6+m7
c22=m5-m3+m2-m1
用上述方案解n=2;矩阵乘法；假定施特拉斯矩阵分割方案仅用于n>=8的矩阵乘法，而对于小于8的矩阵直接利用公式计算；n的值越大，斯拉特森方法更方便；设T(n)表示斯特拉森分治运算法所需时间，因为大的矩阵会被递归分成小矩阵直到每个矩阵的大小小于或等于k，所以T(n)的递归表达式为T(n)=d(n<=k);T(n)=7*t(n/2)+cn2(n平方）（n>k),其中cn2表示完成18次（n/2)(n/2)接矩阵的加减法，以及把大小为N的矩阵分割成小矩阵所需的时间；