Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 24
Текст из файла (страница 24)
Specifically, the algorithm searches A for x in order,considering A[1], A[2], A[3],..., A[n] until either A[i] = x is found or the end of the array isreached. Assume that all possible permutations of the input array are equally likely.e. Suppose that there is exactly one index i such that A[i] = x. What is the expectedrunning time of DETERMINISTIC-SEARCH? What is the worst-case running time ofDETERMINISTIC-SEARCH?f. Generalizing your solution to part (e), suppose that there are k ≥ 1 indices i such thatA[i] = x.
What is the expected running time of DETERMINISTIC-SEARCH? What isthe worst-case running time of DETERMINISTIC-SEARCH? Your answer should bea function of n and k.g. Suppose that there are no indices i such that A[i] = x. What is the expected runningtime of DETERMINISTIC-SEARCH? What is the worst-case running time ofDETERMINISTIC-SEARCH?Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by firstrandomly permuting the input array and then running the deterministic linear search givenabove on the resulting permuted array.h. Letting k be the number of indices i such that A[i] = x, give the worst-case andexpected running times of SCRAMBLE-SEARCH for the cases in which k = 0 and k =1.
Generalize your solution to handle the case in which k ≥ 1.i. Which of the three searching algorithms would you use? Explain your answer.Chapter notesBollobás [44], Hofri [151], and Spencer [283] contain a wealth of advanced probabilistictechniques. The advantages of randomized algorithms are discussed and surveyed by Karp[174] and Rabin [253]. The textbook by Motwani and Raghavan [228] gives an extensivetreatment of randomized algorithms.Several variants of the hiring problem have been widely studied. These problems are morecommonly referred to as "secretary problems." An example of work in this area is the paperby Ajtai, Meggido, and Waarts [12].Part II: Sorting and Order StatisticsChapter ListChapter 6: HeapsortChapter 7: QuicksortChapter 8: Sorting in Linear TimeChapter 9: Medians and Order StatisticsIntroductionThis part presents several algorithms that solve the following sorting problem:•Input: A sequence of n numbersa1, a2, ..., an .•Output: A permutation (reordering).of the input sequence such thatThe input sequence is usually an n-element array, although it may be represented in someother fashion, such as a linked list.The structure of the dataIn practice, the numbers to be sorted are rarely isolated values.
Each is usually part of acollection of data called a record. Each record contains a key, which is the value to be sorted,and the remainder of the record consists of satellite data, which are usually carried aroundwith the key. In practice, when a sorting algorithm permutes the keys, it must permute thesatellite data as well. If each record includes a large amount of satellite data, we often permutean array of pointers to the records rather than the records themselves in order to minimize datamovement.In a sense, it is these implementation details that distinguish an algorithm from a full-blownprogram.
Whether we sort individual numbers or large records that contain numbers isirrelevant to the method by which a sorting procedure determines the sorted order. Thus, whenfocusing on the problem of sorting, we typically assume that the input consists only ofnumbers. The translation of an algorithm for sorting numbers into a program for sortingrecords is conceptually straightforward, although in a given engineering situation there maybe other subtleties that make the actual programming task a challenge.Why sorting?Many computer scientists consider sorting to be the most fundamental problem in the study ofalgorithms.
There are several reasons:•••••Sometimes the need to sort information is inherent in an application. For example, inorder to prepare customer statements, banks need to sort checks by check number.Algorithms often use sorting as a key subroutine. For example, a program that rendersgraphical objects that are layered on top of each other might have to sort the objectsaccording to an "above" relation so that it can draw these objects from bottom to top.We shall see numerous algorithms in this text that use sorting as a subroutine.There is a wide variety of sorting algorithms, and they use a rich set of techniques. Infact, many important techniques used throughout algorithm design are represented inthe body of sorting algorithms that have been developed over the years.
In this way,sorting is also a problem of historical interest.Sorting is a problem for which we can prove a nontrivial lower bound (as we shall doin Chapter 8). Our best upper bounds match the lower bound asymptotically, and sowe know that our sorting algorithms are asymptotically optimal. Moreover, we can usethe lower bound for sorting to prove lower bounds for certain other problems.Many engineering issues come to the fore when implementing sorting algorithms. Thefastest sorting program for a particular situation may depend on many factors, such asprior knowledge about the keys and satellite data, the memory hierarchy (caches andvirtual memory) of the host computer, and the software environment. Many of theseissues are best dealt with at the algorithmic level, rather than by "tweaking" the code.Sorting algorithmsWe introduced two algorithms that sort n real numbers in Chapter 2.
Insertion sort takes Θ(n2)time in the worst case. Because its inner loops are tight, however, it is a fast in-place sortingalgorithm for small input sizes. (Recall that a sorting algorithm sorts in place if only aconstant number of elements of the input array are ever stored outside the array.) Merge sorthas a better asymptotic running time, Θ(n lg n), but the MERGE procedure it uses does notoperate in place.In this part, we shall introduce two more algorithms that sort arbitrary real numbers. Heapsort,presented in Chapter 6, sorts n numbers in place in O(n lg n) time.
It uses an important datastructure, called a heap, with which we can also implement a priority queue.Quicksort, in Chapter 7, also sorts n numbers in place, but its worst-case running time isΘ(n2). Its average-case running time is Θ(n lg n), though, and it generally outperformsheapsort in practice. Like insertion sort, quicksort has tight code, so the hidden constant factorin its running time is small.
It is a popular algorithm for sorting large input arrays.Insertion sort, merge sort, heapsort, and quicksort are all comparison sorts: they determine thesorted order of an input array by comparing elements. Chapter 8 begins by introducing thedecision-tree model in order to study the performance limitations of comparison sorts. Usingthis model, we prove a lower bound of Ω(n lg n) on the worst-case running time of anycomparison sort on n inputs, thus showing that heapsort and merge sort are asymptoticallyoptimal comparison sorts.Chapter 8 then goes on to show that we can beat this lower bound of Ω(n lg n) if we cangather information about the sorted order of the input by means other than comparingelements.
The counting sort algorithm, for example, assumes that the input numbers are in theset {1, 2, ..., k}. By using array indexing as a tool for determining relative order, counting sortcan sort n numbers in Θ(k + n) time. Thus, when k = O(n), counting sort runs in time that islinear in the size of the input array. A related algorithm, radix sort, can be used to extend therange of counting sort.
If there are n integers to sort, each integer has d digits, and each digitis in the set {1, 2, ..., k}, then radix sort can sort the numbers in Θ(d(n + k)) time. When d is aconstant and k is O(n), radix sort runs in linear time. A third algorithm, bucket sort, requiresknowledge of the probabilistic distribution of numbers in the input array. It can sort n realnumbers uniformly distributed in the half-open interval [0, 1) in average-case O(n) time.Order statisticsThe ith order statistic of a set of n numbers is the ith smallest number in the set. One can, ofcourse, select the ith order statistic by sorting the input and indexing the ith element of theoutput. With no assumptions about the input distribution, this method runs in Ω(n lg n) time,as the lower bound proved in Chapter 8 shows.In Chapter 9, we show that we can find the ith smallest element in O(n) time, even when theelements are arbitrary real numbers.
We present an algorithm with tight pseudocode that runsin Θ (n2) time in the worst case, but linear time on average. We also give a more complicatedalgorithm that runs in O(n) worst-case time.BackgroundAlthough most of this part does not rely on difficult mathematics, some sections do requiremathematical sophistication. In particular, the average-case analyses of quicksort, bucket sort,and the order-statistic algorithm use probability, which is reviewed in Appendix C, and thematerial on probabilistic analysis and randomized algorithms in Chapter 5.
The analysis of theworst-case linear-time algorithm for order statistics involves somewhat more sophisticatedmathematics than the other worst-case analyses in this part.Chapter 6: HeapsortOverviewIn this chapter, we introduce another sorting algorithm. Like merge sort, but unlike insertionsort, heapsort's running time is O(n lg n). Like insertion sort, but unlike merge sort, heapsortsorts in place: only a constant number of array elements are stored outside the input array atany time. Thus, heapsort combines the better attributes of the two sorting algorithms we havealready discussed.Heapsort also introduces another algorithm design technique: the use of a data structure, inthis case one we call a "heap," to manage information during the execution of the algorithm.Not only is the heap data structure useful for heapsort, but it also makes an efficient priorityqueue. The heap data structure will reappear in algorithms in later chapters.We note that the term "heap" was originally coined in the context of heapsort, but it has sincecome to refer to "garbage-collected storage," such as the programming languages Lisp andJava provide.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
