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

1、会计学1算法设计算法设计(shj)与分析基础三与分析基础三ch第一页，共44页。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页第二页，共44页。32 also sufficient to sort array of size n (by mergesort).第2页/

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

3、nnxn = bn第5页/共44页第六页，共44页。coefficient in the i-th column of that row 0第6页/共44页第七页，共44页。 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页第八页，共44页。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页第九页，共44页。10nndelete第9页/共44页第十页，共44页。11第10页/共44页第十一页，共44页。12KK第11页/共44页第十二页，共44页。13Bonus: inorder traversal produces sorted list第12页/共44页第十三页，共44页。14n2-3 treesn2-3-4 treesnB-trees第13页/共44页第十四页，共44页。15第14页/共44页第十五页，共44页。16第15页/共44页第十六页，共44页。17第16页/共44页第十七页，共44页。18第17页/共44页第十八页，共44页。1

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

6、。23第22页/共44页第二十三页，共44页。24第23页/共44页第二十四页，共44页。25nB-trees第24页/共44页第二十五页，共44页。26第25页/共44页第二十六页，共44页。27第26页/共44页第二十七页，共44页。28第27页/共44页第二十八页，共44页。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页第二十九页，共44页。30node第29页/共44页第三十页，共44页。

7、31第30页/共44页第三十一页，共44页。32第31页/共44页第三十二页，共44页。33第32页/共44页第三十三页，共44页。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页第三十四页，共44页。35worst-caseC(n) = Both worst-case and average-case efficiency: (nlogn) In-place: yesStability:

8、 no (e.g., 1 1)# nodes at level i 第34页/共44页第三十五页，共44页。36nTwo ways to handle priority queue in which highest priority = smallest number第35页/共44页第三十六页，共44页。37第36页/共44页第三十七页，共44页。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* powerreturn p第37页/共44

9、页第三十八页，共44页。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页第三十九页，共44页。40第39页/共44页第四十页，共44页。412binary rep. of 13: 1 1 0 1 SM SM S SM accumulator: 1 12*a=aa2*a = a3 (a3)2 = a6 (a6)2*a= a13 (computed left-to-right)Efficiency: b M(n) 2b where b = log2 n + 1第40页/共44页第四十一页，共44页。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页/共