算法設計與分析基礎三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.