MIT CLRS NOTES苑炜弢整理Lecture 1Analysis of algorithms theoretical study of computer programming performancemaking things run fast. speed is fun. Problem: sortinginput: sequence of numbers output: permutation Insertions sort (A, n) we use pseudocode Running time: Depends on input(eg , already sorted) Depends on input size( 6 elems vs 6X10000000)parameterize in input size Want upper boundguarantee to userKinds of analysis worst case (usually) T(n)= max time on any input at size n (T(n) is a function)if delete max, T(n) will be a relation not a function Average case (sometimes) T(n)= expected time over all inputs of size n (need assumption of probability distribution) Best case (bogus)cheat with slow alg that work fast on some inputfor insertion sort, what is running time? depends on computerrelative speed (on same machine) run two prog. on the same machineabsolute speed (on diff machines)Insertion sort analysis worst case : input reverse sorted Time= Big Idea: Asymptotic Analysis (huge idea!) Ignore machine dependent constants look at growth of T(n) as Asymptotic analysismajor tool notation: drop low order termsignore leading constantsthe constants will not influent the growth of n. if you compare the order of growth, after some point the slower growth alg will beat the faster growth alg. The constants will matter for the beating point of two diff growth alg, or when two alg have the same growth rate. when we have the input size of 300 or others , we should take the constant into consideration because of the practical situation.Insertion sort analysis: worst case : T(n)= arith analysisthis is upper bound of worst running time. the best running time will be . the growth for these situations are different. the algorithm running time will vary (not a function) but the worst running is a function.average case: T(n)= it is a good sorting alg for small n , but not good for large n.Merge Sort A1.n 1. If n=1, done 2. Resursively sort A 1. and A +1 . n 3. “Merge” 2 sorted sets. T(n)=(1)abuse, constant time+2T(n/2)+(n) T(n)= 2T(n/2)+(n)=(n lgn) better in large n than insert sorting Lecture 2：解递归式（Solving recurrences）替换法Substitution method(most general, can be applied to anything)步骤：1） 猜测解的形式（guess of form of solution）2） 通过数学归纳法，验证猜测结果verify the guess by induction3） 找出使解真正有效的常数（Solvefor constants）举例：如对T(n)=4T(n/2)+n 【T(1) = 】1）猜测：T(n)=用归纳法证明。（1）假设：对Kn: T(k)=Cnot we need some constant, this is strict than. the reason of throwing away bit O notation and using Constants is that we get a stronger induction hypothesis: we can use C constants in our proof. IF we could use big O notation in induction, We could prove that 1+1+1.=O(1), here the constant is changing, so you are cheating.（2）现证明T(n)=cT(n) =4T(n/2n, this is where substitution can be used )+n= 4C (n/2)3+n= (C/2)n3+n= C n3-( (C/2)n3-n) ) Form: desired（期望） - residual（余项）=0 因此，我们可以选择合适的C，使得residual = 0（如c = 2, n0 = 1）（3）目前，我们丢掉了基本情况，因此需要将归纳法建立到基本情况上。（Need to ground induction with base case）初始条件： T(n)= 对 n=n0 for const. n0对 1=n= n0 T(n)= C n3若选择的C够大。的边界不够紧（This bound is not tight.）2）猜测：T(n)=证明：（1）假设T(k)=Ck2 for kn，现证明T(n)=c成立。T(n)=4T(n/2)+n= 4C(n/2)2+n=Cn2+n（但遗憾的是：不可能=Cn2 ！ 假设不够强！）思想：强化归纳假设，减去一个低阶项。通过对更小的值做更强的假设，就可以证明对某个给定值的结论。假设：T(k)=C1K2-C2KT(n) = 4 (C1(n/2)2-C2(n/2) +n=C1n2-(2C2)n + n= C1n2-C2n-(C2n-n)=0 因此选C2=1 and the base case will make the value of C1, C1is constrained by initial conditions. here we learn that the leading term of this alg is determined by the initial conditions, so if you make the initial condition smaller(when n=1, 2 ,3.) , we can improve the algorithms. This is what we learned from solving recurrence problem.【以上均是证明大O。如果要证明theta，则需要证明大O和大mega】递归树方法（Recursion Trees）替换法是一种简单的证明方法，但要有更准确的猜测，有时很难。则，可以画出一个递归树来得到好的猜测。 递归树是对一个算法的递归执行过程的代价（时间）进行建模 递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价n2n2举例：T(n)=T(n/4)+T(n/2)+n2(n/4)2T(n) = = T(n/2)2T(n/4)T(n/8)T(n/16)T(n/8)T(n/2)T(n/4) Tn2(n/4)2(n/8)2(n/8)2(n/16)2(n/2)2(n/4)2= . n2.n2/16+n2/4 = 5n2/16T(n) = n2(1+ ) = 几何级数 主方法（Master Method）主方法应用到如下的递归式形式：T(n)=a T(n/b)+f(n)，其中，b1，f渐进正的函数（存在n0，f(n)0 for ）。是递归树的一个应用，但更精确。1. 主定理的三种情况：（都与函数进行比较）Case 1: 对某常数 = 解释：f(n)不仅小于，而且是多项式地小于。Case 2：对某常数 = Case 3: 对某常数，且对常数c 解释：f(n)不仅要大于，而且是多项式地大于，还要满足“规则性”条件。“规则性”条件：确保f(n)不断变小。2. 举例：1）T(n) = 4T(n/2) + na = 4, b = 2 = n2；f(n) = n Case 1: f(n) = 2）T(n) = 4T(n/2) + n2a =4, b= 2 = n2; f(n) = n2.Case 2: ，即k = 0，因此3）T(n) = 4T(n/2) + n3a =4, b= 2 = n2; f(n) = n3.Case 3:f(n) = (n2+