2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 The method the key inspects a copy of a key's value The static counter comparisons is incremented by any call to a Key comparison operator. For example: P. 275 Static data members must be defined and initialized outside of a class definition. Accordingly, the follow statement is included in the Key implementation file key. c: int Key comparisons =0 e Use the class Timer from Appendix C to provide CPU timing information Most later searching methods require the data to be ordered, so use a list with integer keys in increasing To test both successful and unsuccessful searches, insert only keys containing odd integers into the list If n denotes the number of entries in the list, then the targets for successful searches will be 1, 3, 5,.,2n For unsuccessful searches, the targets will be 0, 2, 4, 6,., 2n In this way we test all possible failures, including targets less than the smallest key in the list, between each pair, and greater than the largest Random . random integer from Appendix Edom To make the test more realistic, use pseudo-random numbers to choose the target, by employing the method 17.3| Binary Search 7.3.1 Ordered Lists P. 278 DEFINITION: An ordered list is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j. P. 278 All List operations except insert and replace apply without modification to an ordered list Methods insert and replace must fail when they would otherwise disturb the order of a list. We implement an ordered list as a class derived from a contiguous List. In this derived class, we shall override the methods insert and replace with new implementations. P. 279 Overloaded insertion: P. 279 Overridden insertion P 280 7.3.2 Binary Search P. 280 Idea: In searching an ordered list, first compare the target to the key in the center of the list. If it is smaller, restrict the search to the left half; otherwise restrict the search to the right half, and repeat. In this way,at each step we reduce the length of the list to be searched by half. Keep two indices, top and bottom, that will bracket the part of the list still to be searched The target key, provided it is present, will be found between the indices bottom and top, inclusive Initialization: Set bottom =0; top= the list size( )-1 Compare target with the Record at the midpoint, mid =(bottom+top)/2 Change the appropriate index top or bottom to restrict the search appropriate half of the list Loop terminates when topsbottom, if it has not terminated earlier by finding the target Make progress toward termination by ensuring that the number of items remaining to be searched top-bottom+l, strictly decreases at each iteration of the process 7.3.3 The Forgetful Version of Binary Search P. 281 Algorithm verification P 282 Nonrecursive Binary Search P. 283 7.3.4 Recognizing Equality in Binary Search P 284 Nonrecursive Version P 285 Algorithm Verification P. 285 7.4 Asy mptotics: The Big-O and Other Notations P 302 7.6.2 Orders of Magnitude P. 304 Assumptions P 305 Orders of Magnitude of Common Functions Polynomials P. 306 ogarithms P 307 L HOpital's Rule P 307 Exponential functions P. 308 The function n log n: The function n log n has strictly greater order of magnitude than n but strictly smaller order of magnitude than any power n' for any r>l Growth Rates of Common Orders P 309-310 7.6.3 The Big-O and Related Notations P. 310 Examples: P. 311 Algorithm Analyses P. 311 7.6.4 Keeping the dominant term: P 311 We define f (n)=g(n)+O(h(n)) to mean that f (n)-g(n) is O(h(n)) More precise form: P 3122008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ The method the key inspects a copy of a key’s value. ⚫ The static counter comparisons is incremented by any call to a Key comparison operator. For example:P. 275 ⚫ Static data members must be defined and initialized outside of a class definition. Accordingly, the following statement is included in the Key implementation file key.c: int Key :: comparisons = 0; ⚫ Use the class Timer from Appendix C to provide CPU timing information. Test Data for Searching P. 275 ⚫ Most later searching methods require the data to be ordered, so use a list with integer keys in increasing order. ⚫ To test both successful and unsuccessful searches, insert only keys containing odd integers into the list. ⚫ If n denotes the number of entries in the list, then the targets for successful searches will be 1, 3, 5,... , 2n − 1. ⚫ For unsuccessful searches, the targets will be 0, 2, 4, 6,... , 2n. ⚫ In this way we test all possible failures, including targets less than the smallest key in the list, between each pair, and greater than the largest. ⚫ To make the test more realistic, use pseudo-random numbers to choose the target, by employing the method Random :: random integer from Appendix B. [7.3] Binary Search 7.3.1 Ordered Lists P. 278 DEFINITION: An ordered list is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j . P. 278 ⚫ All List operations except insert and replace apply without modification to an ordered list. ⚫ Methods insert and replace must fail when they would otherwise disturb the order of a list. ⚫ We implement an ordered list as a class derived from a contiguous List. In this derived class, we shall override the methods insert and replace with new implementations. P. 279 Overloaded insertion: P. 279 Overridden insertion: P. 280 7.3.2 Binary Search P. 280 ⚫ Idea: In searching an ordered list, first compare the target to the key in the center of the list. If it is smaller, restrict the search to the left half; otherwise restrict the search to the right half, and repeat. In this way, at each step we reduce the length of the list to be searched by half. ⚫ Keep two indices, top and bottom, that will bracket the part of the list still to be searched. The target key, provided it is present, will be found between the indices bottom and top, inclusive. ⚫ Initialization: Set bottom = 0; top = the_list.size( ) − 1; ⚫ Compare target with the Record at the midpoint, ⚫ mid = (bottom+top)/2; ⚫ Change the appropriate index top or bottom to restrict the search to the appropriate half of the list. ⚫ Loop terminates when top≤bottom, if it has not terminated earlier by finding the target. ⚫ Make progress toward termination by ensuring that the number of items remaining to be searched, top−bottom+1, strictly decreases at each iteration of the process. 7.3.3 The Forgetful Version of Binary Search P. 281 Algorithm Verification P. 282 Nonrecursive Binary Search P. 283 7.3.4 Recognizing Equality in Binary Search P. 284 Nonrecursive Version P. 285 Algorithm Verification P. 285 [7.4] Asymptotics: The Big-O and Other Notations P. 302 7.6.2 Orders of Magnitude P. 304 Assumptions P. 305 Orders of Magnitude of Common Functions Polynomials P. 306 Logarithms P. 307 L’Hôpital’s Rule P. 307 Exponential functions P. 308 The function n log n: The function n log n has strictly greater order of magnitude than n but strictly smaller order of magnitude than any power nr for any r>1. Growth Rates of Common Orders P. 309-310 7.6.3 The Big-O and Related Notations P. 310 Examples: P. 311 Algorithm Analyses P. 311 7.6.4 Keeping the dominant term: P. 311 We define f (n) = g (n) + O(h (n)) to mean that f (n) − g(n) is O(h(n)) . More precise form: P.312