Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 37
Текст из файла (страница 37)
Find the algorithm that implements each of the following methods with thebest asymptotic worst-case running time, and analyze the running times of the algorithms interms of n and i.a. Sort the numbers, and list the i largest.b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.c. Use an order-statistic algorithm to find the ith largest number, partition around thatnumber, and sort the i largest numbers.Problems 9-2: Weighted medianFor n distinct elements x1, x2, ..., xn with positive weights w1, w2, ..., wn such thatweighted (lower) median is the element xk satisfying, theanda. Argue that the median of x1, x2, ..., xn is the weighted median of the xi with weights wi= 1/n for i = 1,2, ..., n.b. Show how to compute the weighted median of n elements in O(n lg n) worst-case timeusing sorting.c.
Show how to compute the weighted median in Θ(n) worst-case time using a lineartime median algorithm such as SELECT from Section 9.3.The post-office location problem is defined as follows. We are given n points p1, p2, ..., pnwith associated weights w1, w2, ..., wn. We wish to find a point p (not necessarily one of theinput points) that minimizes the sum, where d(a, b) is the distance between pointsa and b.d. Argue that the weighted median is a best solution for the 1-dimensional post-officelocation problem, in which points are simply real numbers and the distance betweenpoints a and b is d(a, b) = |a - b|.e.
Find the best solution for the 2-dimensional post-office location problem, in which thepoints are (x, y) coordinate pairs and the distance between points a = (x1, y1) and b =(x2, y2) is the Manhattan distance given by d(a, b) = |x1 - x2| + |y1 - y2|.Problems 9-3: Small order statisticsThe worst-case number T(n) of comparisons used by SELECT to select the ith order statisticfrom n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notationis rather large.
When i is small relative to n, we can implement a different procedure that usesSELECT as a subroutine but makes fewer comparisons in the worst case.a. Describe an algorithm that uses Ui(n) comparisons to find the ith smallest of nelements, where(Hint: Begin with ⌊n/2⌋ disjoint pairwise comparisons, and recurse on the setcontaining the smaller element from each pair.)b. Show that, if i < n/2, then Ui(n) = n + O(T (2i) lg(n/i)).c. Show that if i is a constant less than n/2, then Ui(n) = n + O(lg n).d. Show that if i = n/k for k ≥ 2, then Ui(n) = n + O(T (2n/k) lg k).[1]Because of our assumption that the numbers are distinct, we can say "greater than" and "lessthan" without being concerned about equality.Chapter notesThe worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt,Rivest, and Tarjan [43].
The fast average-time version is due to Hoare [146]. Floyd and Rivest[92] have developed an improved average-time version that partitions around an elementrecursively selected from a small sample of the elements.It is still unknown exactly how many comparisons are needed to determine the median. Alower bound of 2n comparisons for median finding was given by Bent and John [38]. Anupper bound of 3n was given by Schonhage, Paterson, and Pippenger [265]. Dor and Zwick[79] have improved on both of these bounds; their upper bound is slightly less than 2.95n andthe lower bound is slightly more than 2n.
Paterson [239] describes these results along withother related work.Part III: Data StructuresChapter ListChapter 10: Elementary Data StructuresChapter 11: Hash TablesChapter 12: Binary Search TreesChapter 13: Red-Black TreesChapter 14: Augmenting Data StructuresIntroductionSets are as fundamental to computer science as they are to mathematics. Whereasmathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, orotherwise change over time. We call such sets dynamic.
The next five chapters present somebasic techniques for representing finite dynamic sets and manipulating them on a computer.Algorithms may require several different types of operations to be performed on sets. Forexample, many algorithms need only the ability to insert elements into, delete elements from,and test membership in a set. A dynamic set that supports these operations is called adictionary.
Other algorithms require more complicated operations. For example, min-priorityqueues, which were introduced in Chapter 6 in the context of the heap data structure, supportthe operations of inserting an element into and extracting the smallest element from a set. Thebest way to implement a dynamic set depends upon the operations that must be supported.Elements of a dynamic setIn a typical implementation of a dynamic set, each element is represented by an object whosefields can be examined and manipulated if we have a pointer to the object. (Section 10.3discusses the implementation of objects and pointers in programming environments that donot contain them as basic data types.) Some kinds of dynamic sets assume that one of theobject's fields is an identifying key field.
If the keys are all different, we can think of thedynamic set as being a set of key values. The object may contain satellite data, which arecarried around in other object fields but are otherwise unused by the set implementation. Itmay also have fields that are manipulated by the set operations; these fields may contain dataor pointers to other objects in the set.Some dynamic sets presuppose that the keys are drawn from a totally ordered set, such as thereal numbers, or the set of all words under the usual alphabetic ordering.
(A totally ordered setsatisfies the trichotomy property, defined on page 49.) A total ordering allows us to define theminimum element of the set, for example, or speak of the next element larger than a givenelement in a set.Operations on dynamic setsOperations on a dynamic set can be grouped into two categories: queries, which simply returninformation about the set, and modifying operations, which change the set. Here is a list oftypical operations. Any specific application will usually require only a few of these to beimplemented.SEARCH(S, k)•A query that, given a set S and a key value k, returns a pointer x to an element in Ssuch that key[x] = k, or NIL if no such element belongs to S.INSERT(S, x)•A modifying operation that augments the set S with the element pointed to by x. Weusually assume that any fields in element x needed by the set implementation havealready been initialized.DELETE(S, x)•A modifying operation that, given a pointer x to an element in the set S, removes xfrom S.
(Note that this operation uses a pointer to an element x, not a key value.)MINIMUM(S)•A query on a totally ordered set S that returns a pointer to the element of S with thesmallest key.MAXIMUM(S)•A query on a totally ordered set S that returns a pointer to the element of S with thelargest key.SUCCESSOR(S, x)•A query that, given an element x whose key is from a totally ordered set S, returns apointer to the next larger element in S, or NIL if x is the maximum element.PREDECESSOR(S, x)•A query that, given an element x whose key is from a totally ordered set S, returns apointer to the next smaller element in S, or NIL if x is the minimum element.The queries SUCCESSOR and PREDECESSOR are often extended to sets with non-distinctkeys.
For a set on n keys, the normal presumption is that a call to MINIMUM followed by n 1 calls to SUCCESSOR enumerates the elements in the set in sorted order.The time taken to execute a set operation is usually measured in terms of the size of the setgiven as one of its arguments. For example, Chapter 13 describes a data structure that cansupport any of the operations listed above on a set of size n in time O(lg n).Overview of Part IIIChapters 10–14 describe several data structures that can be used to implement dynamic sets;many of these will be used later to construct efficient algorithms for a variety of problems.Another important data structure—the heap—has already been introduced in Chapter 6.Chapter 10 presents the essentials of working with simple data structures such as stacks,queues, linked lists, and rooted trees.
It also shows how objects and pointers can beimplemented in programming environments that do not support them as primitives. Much ofthis material should be familiar to anyone who has taken an introductory programmingcourse.Chapter 11 introduces hash tables, which support the dictionary operations INSERT,DELETE, and SEARCH. In the worst case, hashing requires Θ(n) time to perform a SEARCHoperation, but the expected time for hash-table operations is O(1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
