算法设计与分析基础三ch学习教案

1、会计学1算法算法(sun f)设计与分析基础三设计与分析基础三ch第一页，共45页。2problem)nchecking if all elements are distinct (element uniqueness)Also: nTopological sorting helps solving some problems for dags.nPresorting is used in many geometric algorithms.第1页/共44页第二页，共45页。3also sufficient to sort array of size n (by mergesort).第2页/

2、共44页第三页，共45页。4(nlog n) Good or bad?Why do we have our dictionaries, telephone directories, etc. sorted?第3页/共44页第四页，共45页。5nAnother algorithm? Hashing第4页/共44页第五页，共45页。a11x1 + a12x2 + + a1nxn = b1 a1,1x1+ a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 a22x2 + + a2nxn = b2an1x1 + an2x2 + + annxn = bna

3、nnxn = bn第5页/共44页第六页，共45页。coefficient in the i-th column of that row 0第6页/共44页第七页，共45页。 0 5 -1/2 2 0 0 -6/5 -36/5Backward substitution x3= (-36/5) / (-6/5) = 6x2= (2+(1/2)*6) / 5 = 1x1= (6 6 + 4*1)/2 = 2第7页/共44页第八页，共45页。for k j +1 to n dot t + Aj, k * xk xj (Aj, n+1 - t) / Aj, j Efficiency: (n3) + (

4、n2) = (n3)第8页/共44页第九页，共45页。10ndelete第9页/共44页第十页，共45页。11第10页/共44页第十一页，共45页。12KK第11页/共44页第十二页，共45页。13Bonus: inorder traversal produces sorted list第12页/共44页第十三页，共45页。14of a search treen2-3 treesn2-3-4 treesnB-trees第13页/共44页第十四页，共45页。15第14页/共44页第十五页，共45页。16第15页/共44页第十六页，共45页。17第16页/共44页第十七页，共45页。18第17页/

5、共44页第十八页，共45页。19第18页/共44页第十九页，共45页。20第19页/共44页第二十页，共45页。21nfrequent rotationsncomplexitynA similar idea: red-black trees (height of subtrees is allowed to differ by up to a factor of 2) 第20页/共44页第二十一页，共45页。22Note: Every node in a classical binary search tree is a 2-nodek1 k2 kn-1 k1k1, k2 ) kn-1第21页

6、/共44页第二十二页，共45页。23第22页/共44页第二十三页，共45页。24第23页/共44页第二十四页，共45页。25nB-trees第24页/共44页第二十五页，共45页。26第25页/共44页第二十六页，共45页。27第26页/共44页第二十七页，共45页。28第27页/共44页第二十八页，共45页。29nParent of node j is at j/2nParental nodes are represented in the first n/2locations9153421 2 3 4 5 69 5 3 1 4 2第28页/共44页第二十九页，共45页。30node第29页

7、/共44页第三十页，共45页。31第30页/共44页第三十一页，共45页。32第31页/共44页第三十二页，共45页。33第32页/共44页第三十三页，共45页。34 9 2 8 6 5 75 6 7 2 | 8 9 9 6 8 2 5 77 6 5 2 | 8 9 2 6 5 | 7 8 96 2 5 | 7 8 95 2 | 6 7 8 95 2 | 6 7 8 9 2 | 5 6 7 8 9第33页/共44页第三十四页，共45页。35worst-caseC(n) = Both worst-case and average-case efficiency: (nlogn) In-place

8、: yesStability: no (e.g., 1 1)# nodes at level i 第34页/共44页第三十五页，共45页。36nTwo ways to handle priority queue in which highest priority = smallest number第35页/共44页第三十六页，共45页。37第36页/共44页第三十七页，共45页。38i 1 to n do power 1 power power * x for j 1 to i dop p + ai * powerpower power * x return pp p + ai* powerr

9、eturn p第37页/共44页第三十八页，共45页。39 Same sequence of computations are obtained by simply arranging the coefficient in a table and proceeding as follows:coefficients2-1 3 1-5x=3第38页/共44页第三十九页，共45页。40第39页/共44页第四十页，共45页。412binary rep. of 13: 1 1 0 1 SM SM S SM accumulator: 1 12*a=aa2*a = a3 (a3)2 = a6 (a6)2*

10、a= a13 (computed left-to-right)Efficiency: b M(n) 2b where b = log2 n + 1第40页/共44页第四十一页，共45页。421 a8 a4 a2a : a2 i terms a8* a4*a : product (computed right-to-left)Efficiency: same as that of left-to-right binary exponentiation第41页/共44页第四十二页，共45页。43第42页/共44页第四十三页，共45页。44nlinear programmingnreduction to graph problems (e.g.