《算法设计与分析基础第三版PPTch06.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析基础第三版PPTch06.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1Transform and ConquerThis group of techniques solves a problem by a This group of techniques solves a problem by a transformationtransformation to tobba simpler/more convenient instance of the same a simpler/more convenient instance of the same problem(problem(instance simplificationinstance simpl
2、ification)bba different representation of the same instance a different representation of the same instance(representation changerepresentation change)bba different problem for which an algorithm is a different problem for which an algorithm is already available(already available(problem reductionpr
3、oblem reduction)2Instance simplification-PresortingSolve a problems instance by transforming it intoSolve a problems instance by transforming it intoanother simpler/easier instance of the same problemanother simpler/easier instance of the same problemPresortingPresortingMany problems involving lists
4、 are easier when list is sorted,e.g.Many problems involving lists are easier when list is sorted,e.g.bbsearching searching bbcomputing the median(selection problem)computing the median(selection problem)bbchecking if all elements are distinct(element uniqueness)checking if all elements are distinct(
5、element uniqueness)Also:Also:bbTopological sorting helps solving some problems for dags.Topological sorting helps solving some problems for dags.bbPresorting is used in many geometric algorithms.Presorting is used in many geometric algorithms.3How fast can we sort?Efficiency of algorithms involving
6、sorting depends onEfficiency of algorithms involving sorting depends onefficiency of sorting.efficiency of sorting.TheoremTheorem(see Sec.11.2):(see Sec.11.2):loglog2 2 n n!n n loglog2 2 n n comparisons are comparisons are necessary in the worst case to sort a list of size necessary in the worst cas
7、e to sort a list of size n n by by anyany comparison-based parison-based algorithm.Note:About Note:About n nloglog2 2 n n comparisons are also sufficient to sort array comparisons are also sufficient to sort array of size of size n n(by mergesort).(by mergesort).4Searching with presortingProblem:Sea
8、rch for a given Problem:Search for a given K K in A0.in A0.n n-1-1 Presorting-based algorithm:Presorting-based algorithm:Stage 1 Sort the array by an efficient sorting algorithmStage 1 Sort the array by an efficient sorting algorithm Stage 2 Apply binary search Stage 2 Apply binary search Efficiency
9、:Efficiency:(n nlog log n n)+O(log)+O(log n n)=)=(n nlog log n n)Good or bad?Good or bad?Why do we have our dictionaries,telephone directories,etc.Why do we have our dictionaries,telephone directories,etc.sorted?sorted?5Element Uniqueness with presortingbbPresorting-basedPresorting-based algorithm a
10、lgorithm Stage 1:sort by efficient sorting algorithm(e.g.mergesort)Stage 1:sort by efficient sorting algorithm(e.g.mergesort)Stage 2:scan array to check pairs of Stage 2:scan array to check pairs of adjacentadjacent elements elements Efficiency Efficiency:(n nlog log n n)+O()+O(n n)=)=(n nlog log n
11、n)bbBrute force algorithm Brute force algorithm Compare all pairs of elements Compare all pairs of elements Efficiency:O(Efficiency:O(n n2 2)bbAnother algorithm?HashingAnother algorithm?Hashing Instance simplification Gaussian EliminationGiven:A system of Given:A system of n n linear equations in li
12、near equations in n n unknowns with an unknowns with an arbitrary coefficient matrix.arbitrary coefficient matrix.Transform to:An equivalent system of Transform to:An equivalent system of n n linear equations in linear equations in n n unknowns with an upper triangular coefficient matrix.unknowns wi
13、th an upper triangular coefficient matrix.Solve the latter by substitutions starting with the last equation Solve the latter by substitutions starting with the last equation and moving up to the first one.and moving up to the first one.a a1111x x1 1+a a1212x x2 2+a a1 1n nx xn n=b b1 1 a a1,11,1x x1
14、 1+a a1212x x2 2+a a1 1n nx xn n=b b1 1 a a2121x x1 1+a a2222x x2 2+a a2 2n nx xn n=b b2 2 a a2222x x2 2+a a2 2n nx xn n=b b2 2 a an n1 1x x1 1+a an n2 2x x2 2 +a annnnx xn n=b bn n a annnnx xn n=b bn n 6 Gaussian Elimination(cont.)The transformation is accomplished by a sequence of elementary The t
15、ransformation is accomplished by a sequence of elementary operations on the systems coefficient matrix (which dont operations on the systems coefficient matrix (which dont change the systems solution):change the systems solution):forfor i i 1 to 1 to n-n-1 1 dodo replace each of the subsequent rows(
16、i.e.,rows replace each of the subsequent rows(i.e.,rows i i+1,+1,n n)by)by a difference between that row and an appropriate multiple a difference between that row and an appropriate multiple of the of the i-i-th row to make the new coefficient in the th row to make the new coefficient in the i-i-tht
17、h column column of that row 0 of that row 07 Example of Gaussian EliminationSolve 2Solve 2x x1 1-4-4x x2 2 +x x3 3=6 =6 3 3x x1 1-x x2 2 +x x3 3=11=11 x x1 1+x x2 2 -x x3 3=-3=-3 Gaussian eliminationGaussian elimination 2 2 -4-4 1 6 2 1 6 2 -4-4 1 1 6 6 3 -1 1 11 row2 (3/2)*row1 0 5 -1/2 2 3 -1 1 11
18、 row2 (3/2)*row1 0 5 -1/2 2 1 1 -1 1 1 -1 -3 row3 (1/2)*row1 0 3 -3/2 -6 row3(3/5)*row2-3 row3 (1/2)*row1 0 3 -3/2 -6 row3(3/5)*row2 2 2 -4-4 1 1 6 6 0 5 -1/2 2 0 5 -1/2 2 0 0 -6/5-36/5 0 0 -6/5-36/5 Backward substitutionBackward substitution x x3 3=(-36/5)/(-6/5)=6=(-36/5)/(-6/5)=6 x x2 2=(2+(1/2)*
19、6)/5=1=(2+(1/2)*6)/5=1 x x1 1=(6 6+4*1)/2=2=(6 6+4*1)/2=28 Pseudocode and Efficiency of Gaussian EliminationStage 1:Reduction to an upper-triangular matrixStage 1:Reduction to an upper-triangular matrixforfor i i 1 1 toto n-n-1 1 dodo for for j j i i+1+1 toto n n dodo for for k k i i toto n+n+1 1 do
20、do A A j j,k k A A j j,k k-A A i i,k k *A*A j j,i i/A A i i,i i /improve!/improve!Stage 2:Back substitutionsStage 2:Back substitutionsforfor j j n n downto downto 1 1 dodo t t 0 0 forfor k k j j+1+1 toto n n dodo t t t t+A A j j,k k*x x k k x x j j (A A j j,n n+1-+1-t t)/)/A A j j,j j Efficiency:Eff
21、iciency:(n n3 3)+(n n2 2)=(n n3 3)9 10Searching ProblemProblemProblem:Given a(multi)set:Given a(multi)set S S of keys and a search of keys and a search key key K K,find an occurrence of,find an occurrence of K K in in S S,if any,if anybbSearching must be considered in the context of:Searching must b
22、e considered in the context of:file size(internal vs.external)file size(internal vs.external)dynamics of data(static vs.dynamic)dynamics of data(static vs.dynamic)bbDictionary operations(dynamic data):Dictionary operations(dynamic data):find(search)find(search)insertinsert deletedelete 11Taxonomy of
23、 Searching AlgorithmsbbList searchingList searching sequential searchsequential search binary searchbinary search interpolation searchinterpolation searchbbTree searching Tree searching binary search treebinary search tree binary balanced trees:AVL trees,red-black treesbinary balanced trees:AVL tree
24、s,red-black trees multiway balanced trees:2-3 trees,2-3-4 trees,B treesmultiway balanced trees:2-3 trees,2-3-4 trees,B treesbbHashingHashing open hashing(separate chaining)open hashing(separate chaining)closed hashing(open addressing)closed hashing(open addressing)12Binary Search TreeArrange keys in
25、 a binary tree with the Arrange keys in a binary tree with the binary search binary search tree propertytree property:KKExample:5,3,1,10,12,7,9Example:5,3,1,10,12,7,9 13Dictionary Operations on Binary Search TreesSearching straightforwardSearching straightforwardInsertion search for key,insert at le
26、af where search terminatedInsertion search for key,insert at leaf where search terminatedDeletion 3 cases:Deletion 3 cases:deleting key at a leafdeleting key at a leafdeleting key at node with single childdeleting key at node with single childdeleting key at node with two childrendeleting key at nod
27、e with two children Efficiency depends of the trees height:Efficiency depends of the trees height:loglog2 2 n n h h n n-1,-1,with height average(random files)be about 3with height average(random files)be about 3loglog2 2 n n Thus all three operations have Thus all three operations have worst case ef
28、ficiency:worst case efficiency:(n n)average case efficiency:average case efficiency:(log(log n n)BonusBonus:inorder traversal produces sorted list:inorder traversal produces sorted list 14Balanced Search Trees Attractiveness of Attractiveness of binary search tree binary search tree is marred by the
29、 bad(linear)is marred by the bad(linear)worst-case efficiency.Two ideas to overcome it are:worst-case efficiency.Two ideas to overcome it are:bb to rebalance binary search tree when a new insertion to rebalance binary search tree when a new insertion makes the tree“too unbalanced”makes the tree“too
30、unbalanced”AVL treesAVL trees red-black treesred-black treesbb to allow more than one key per node of a search tree to allow more than one key per node of a search tree 2-3 trees2-3 trees 2-3-4 trees2-3-4 trees B-treesB-trees 15Balanced trees:AVL treesDefinitionDefinition An An AVL treeAVL tree is a
31、 binary search tree in which,for is a binary search tree in which,for every node,the difference between the heights of its left and every node,the difference between the heights of its left and right subtrees,called the right subtrees,called the balance factorbalance factor,is at most 1(with,is at m
32、ost 1(with the height of an empty tree defined as-1)the height of an empty tree defined as-1)Tree(a)is an AVL tree;tree(b)is not an AVL treeTree(a)is an AVL tree;tree(b)is not an AVL tree 16RotationsIf a key insertion violates the balance requirement at some If a key insertion violates the balance r
33、equirement at some node,the subtree rooted at that node is transformed via one of node,the subtree rooted at that node is transformed via one of the four the four rotations.rotations.(The rotation is always performed for a(The rotation is always performed for a subtree rooted at an“unbalanced”node c
34、losest to the new leaf.)subtree rooted at an“unbalanced”node closest to the new leaf.)Single Single R-R-rotationrotationDouble Double LR-LR-rotationrotation 17General case:Single R-rotation 18General case:Double LR-rotation 19AVL tree construction-an exampleConstruct an AVL tree for the list 5,6,8,3
35、,2,4,7 Construct an AVL tree for the list 5,6,8,3,2,4,7 20AVL tree construction-an example(cont.)21Analysis of AVL treesbbh h 1.4404 1.4404 loglog2 2(n n+2)-1.3277 +2)-1.3277 average height:1.01 average height:1.01 loglog2 2n n+0.1 for large 0.1 for large n n(found empirically)(found empirically)bbS
36、earch and insertion are O(Search and insertion are O(log log n n)bbDeletion is more complicated but is also O(Deletion is more complicated but is also O(log log n n)bbDisadvantages:Disadvantages:frequent rotationsfrequent rotations complexitycomplexitybbA similar idea:A similar idea:red-black treesr
37、ed-black trees(height of subtrees is allowed to (height of subtrees is allowed to differ by up to a factor of 2)differ by up to a factor of 2)22Multiway Search TreesDefinitionDefinition A A multiway search treemultiway search tree is a search tree that allows is a search tree that allowsmore than on
38、e key in the same node of the tree.more than one key in the same node of the tree.DefinitionDefinition A node of a search tree is called an A node of a search tree is called an n n-nodenode if it if it contains contains n-n-1 ordered keys(which divide the entire key range 1 ordered keys(which divide
39、 the entire key range into into n n intervals pointed to by the nodes intervals pointed to by the nodes n n links to its children):links to its children):Note:Every node in a classical binary search tree is a 2-nodeNote:Every node in a classical binary search tree is a 2-node k1 k2 kn-1 k1k1,k2)kn-1
40、 232-3 Tree DefinitionDefinition A A 2-3 tree2-3 tree is a search tree that is a search tree thatbb may have 2-nodes and 3-nodes may have 2-nodes and 3-nodesbb height-balanced(all leaves are on the same level)height-balanced(all leaves are on the same level)A 2-3 tree is constructed by successive in
41、sertions of keys given,A 2-3 tree is constructed by successive insertions of keys given,with a new key always inserted into a leaf of the tree.If the leaf with a new key always inserted into a leaf of the tree.If the leaf is a 3-node,its split into two with the middle key promoted to is a 3-node,its
42、 split into two with the middle key promoted to the parent.the parent.242-3 tree construction an exampleConstruct a 2-3 tree the list 9,5,8,3,2,4,7Construct a 2-3 tree the list 9,5,8,3,2,4,7 25Analysis of 2-3 treesbbloglog3 3(n n+1)-1+1)-1 h h loglog2 2(n n+1)-1+1)-1bbSearch,insertion,and deletion a
43、re in Search,insertion,and deletion are in (log log n n)bbThe idea of 2-3 tree can be generalized by allowing more The idea of 2-3 tree can be generalized by allowing more keys per node keys per node 2-3-4 trees 2-3-4 trees B-treesB-trees 26Heaps and HeapsortDefinitionDefinition A A heapheap is a bi
44、nary tree with keys at its nodes(one is a binary tree with keys at its nodes(one key per node)such that:key per node)such that:bbIt is essentially complete,i.e.,all its levels are full except It is essentially complete,i.e.,all its levels are full except possibly the last level,where only some right
45、most keys may possibly the last level,where only some rightmost keys may be missingbe missingbbThe key at each node is The key at each node is keys at its children keys at its children 27Illustration of the heaps definitiona heapa heapnot a heapnot a heapnot a heapnot a heapNote:Heaps elements are o
46、rdered top down(along any path Note:Heaps elements are ordered top down(along any path down from its root),but they are not ordered left to right down from its root),but they are not ordered left to right 28Some Important Properties of a HeapbbGiven Given n,n,there exists a unique binary tree with t
47、here exists a unique binary tree with n n nodes that nodes that is essentially complete,with is essentially complete,with h h=loglog2 2 n n bbThe root contains the largest keyThe root contains the largest keybbThe subtree rooted at any node of a heap is also a heapThe subtree rooted at any node of a
48、 heap is also a heapbbA heap can be represented as an arrayA heap can be represented as an array 29Heaps Array RepresentationStore heaps elements in an array(whose elements indexed,Store heaps elements in an array(whose elements indexed,for convenience,1 to for convenience,1 to n n)in top-down left-
49、to-right order)in top-down left-to-right orderExample:Example:bbLeft child of node Left child of node j j is at 2 is at 2j jbbRight child of node Right child of node j j is at 2 is at 2j j+1+1bbParent of node Parent of node j j is at is at j j/2/2 bbParental nodes are represented in the first Parent
50、al nodes are represented in the first n n/2/2 locationslocations9153421 2 3 4 5 69 5 3 1 4 2 30Step 0:Initialize the structure with keys in the order givenStep 0:Initialize the structure with keys in the order givenStep 1:Starting with the last(rightmost)parental node,fix the Step 1:Starting with th