Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 10
Текст из файла (страница 10)
Argue that the worst-case runningtime of binary search is Θ(lg n).Exercises 2.3-6Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1uses a linear search to scan (backward) through the sorted subarray A[1 j - 1]. Can we use abinary search (see Exercise 2.3-5) instead to improve the overall worst-case running time ofinsertion sort to Θ(n lg n)?Exercises 2.3-7:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,determines whether or not there exist two elements in S whose sum is exactly x.Problems 2-1: Insertion sort on small arrays in merge sortAlthough merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in insertion sort make it faster for small n. Thus, it makes senseto use insertion sort within merge sort when subproblems become sufficiently small.
Considera modification to merge sort in which n/k sublists of length k are sorted using insertion sortand then merged using the standard merging mechanism, where k is a value to be determined.a. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk)worst-case time.b.
Show that the sublists can be merged in Θ(n lg (n/k) worst-case time.c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what isthe largest asymptotic (Θnotation) value of k as a function of n for which the modifiedalgorithm has the same asymptotic running time as standard merge sort?d. How should k be chosen in practice?Problems 2-2: Correctness of bubblesortBubblesort is a popular sorting algorithm. It works by repeatedly swapping adjacent elementsthat are out of order.BUBBLESORT(A)1 for i ← 1 to length[A]2do for j ← length[A] downto i + 13do if A[j] < A[j - 1]4then exchange A[j] ↔ A[j - 1]a.
Let A′ denote the output of BUBBLESORT(A). To prove that BUBBLESORT iscorrect, we need to prove that it terminates and that(2.3)b. where n = length[A]. What else must be proved to show that BUBBLESORT actuallysorts?The next two parts will prove inequality (2.3).b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loopinvariant holds. Your proof should use the structure of the loop invariant proofpresented in this chapter.c. Using the termination condition of the loop invariant proved in part (b), state a loopinvariant for the for loop in lines 1-4 that will allow you to prove inequality (2.3).Your proof should use the structure of the loop invariant proof presented in thischapter.d.
What is the worst-case running time of bubblesort? How does it compare to therunning time of insertion sort?Problems 2-3: Correctness of Horner's ruleThe following code fragment implements Horner's rule for evaluating a polynomialgiven the coefficients a0, a1, . .
. , an and a value for x:12345y ← 0i ← nwhile i ≥ 0do y ← ai + x · yi ← i - 1a. What is the asymptotic running time of this code fragment for Horner's rule?b. Write pseudocode to implement the naive polynomial-evaluation algorithm thatcomputes each term of the polynomial from scratch. What is the running time of thisalgorithm? How does it compare to Horner's rule?c.
Prove that the following is a loop invariant for the while loop in lines 3 -5.At the start of each iteration of the while loop of lines 3-5,Interpret a summation with no terms as equaling 0. Your proof should follow thestructure of the loop invariant proof presented in this chapter and should show that, attermination,.d. Conclude by arguing that the given code fragment correctly evaluates a polynomialcharacterized by the coefficients a0, a1, . . . , an.Problems 2-4: InversionsLet A[1 n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) iscalled an inversion of A.a. List the five inversions of the array 2, 3, 8, 6, 1 .b.
What array with elements from the set {1, 2, . . . , n} has the most inversions? Howmany does it have?c. What is the relationship between the running time of insertion sort and the number ofinversions in the input array? Justify your answer.d. Give an algorithm that determines the number of inversions in any permutation on nelements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)[6]We shall see in Chapter 3 how to formally interpret equations containing Θ-notation.The expression ⌈x⌉ denotes the least integer greater than or equal to x, and ⌊x⌋ denotes thegreatest integer less than or equal to x. These notations are defined in Chapter 3.
The easiest[7]way to verify that setting q to ⌊( p + r)/2⌋ yields subarrays A[pq] and A[q + 1r] of sizes⌈n/2⌉ and ⌊n/2⌋, respectively, is to examine the four cases that arise depending on whethereach of p and r is odd or even.[8]It is unlikely that the same constant exactly represents both the time to solve problems ofsize 1 and the time per array element of the divide and combine steps. We can get around thisproblem by letting c be the larger of these times and understanding that our recurrence givesan upper bound on the running time, or by letting c be the lesser of these times andunderstanding that our recurrence gives a lower bound on the running time. Both bounds willbe on the order of n lg n and, taken together, give a Θ(n lg n) running time.Chapter notesIn 1968, Knuth published the first of three volumes with the general title The Art of ComputerProgramming [182, 183, 185].
The first volume ushered in the modern study of computeralgorithms with a focus on the analysis of running time, and the full series remains anengaging and worthwhile reference for many of the topics presented here. According toKnuth, the word "algorithm" is derived from the name "al-Khowârizmî," a ninth-centuryPersian mathematician.Aho, Hopcroft, and Ullman [5] advocated the asymptotic analysis of algorithms as a means ofcomparing relative performance. They also popularized the use of recurrence relations todescribe the running times of recursive algorithms.Knuth [185] provides an encyclopedic treatment of many sorting algorithms.
His comparisonof sorting algorithms (page 381) includes exact step-counting analyses, like the one weperformed here for insertion sort. Knuth's discussion of insertion sort encompasses severalvariations of the algorithm. The most important of these is Shell's sort, introduced by D. L.Shell, which uses insertion sort on periodic subsequences of the input to produce a fastersorting algorithm.Merge sort is also described by Knuth.
He mentions that a mechanical collator capable ofmerging two decks of punched cards in a single pass was invented in 1938. J. von Neumann,one of the pioneers of computer science, apparently wrote a program for merge sort on theEDVAC computer in 1945.The early history of proving programs correct is described by Gries [133], who credits P.Naur with the first article in this field. Gries attributes loop invariants to R. W. Floyd. Thetextbook by Mitchell [222] describes more recent progress in proving programs correct.Chapter 3: Growth of FunctionsOverviewThe order of growth of the running time of an algorithm, defined in Chapter 2, gives a simplecharacterization of the algorithm's efficiency and also allows us to compare the relativeperformance of alternative algorithms.
Once the input size n becomes large enough, mergesort, with its Θ(n lg n) worst-case running time, beats insertion sort, whose worst-case runningtime is Θ(n2). Although we can sometimes determine the exact running time of an algorithm,as we did for insertion sort in Chapter 2, the extra precision is not usually worth the effort ofcomputing it. For large enough inputs, the multiplicative constants and lower-order terms ofan exact running time are dominated by the effects of the input size itself.When we look at input sizes large enough to make only the order of growth of the runningtime relevant, we are studying the asymptotic efficiency of algorithms. That is, we areconcerned with how the running time of an algorithm increases with the size of the input inthe limit, as the size of the input increases without bound.
Usually, an algorithm that isasymptotically more efficient will be the best choice for all but very small inputs.This chapter gives several standard methods for simplifying the asymptotic analysis ofalgorithms. The next section begins by defining several types of "asymptotic notation," ofwhich we have already seen an example in Θ-notation. Several notational conventions usedthroughout this book are then presented, and finally we review the behavior of functions thatcommonly arise in the analysis of algorithms.3.1 Asymptotic notationThe notations we use to describe the asymptotic running time of an algorithm are defined interms of functions whose domains are the set of natural numbers N = {0, 1, 2, ...}.
Suchnotations are convenient for describing the worst-case running-time function T (n), which isusually defined only on integer input sizes. It is sometimes convenient, however, to abuseasymptotic notation in a variety of ways. For example, the notation is easily extended to thedomain of real numbers or, alternatively, restricted to a subset of the natural numbers. It isimportant, however, to understand the precise meaning of the notation so that when it isabused, it is not misused. This section defines the basic asymptotic notations and alsointroduces some common abuses.Θ-notationIn Chapter 2, we found that the worst-case running time of insertion sort is T (n) = Θ(n2).
Letus define what this notation means. For a given function g(n), we denote by Θ(g(n)) the set offunctionsΘ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)for all n ≥ n0}.[1]A function f(n) belongs to the set Θ(g(n)) if there exist positive constants c1 and c2 such that itcan be "sandwiched" between c1g(n) and c2g(n), for sufficiently large n. Because Θ(g(n)) is aset, we could write "f(n) Θ(g(n))" to indicate that f(n) is a member of Θ(g(n)). Instead, wewill usually write "f(n) = Θ(g(n))" to express the same notion.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
