Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 5
Текст из файла (страница 5)
The first, known asinsertion sort, takes time roughly equal to c1n2 to sort n items, where c1 is a constant that doesnot depend on n. That is, it takes time roughly proportional to n2. The second, merge sort,takes time roughly equal to c2n lg n, where lg n stands for log2 n and c2 is another constantthat also does not depend on n. Insertion sort usually has a smaller constant factor than mergesort, so that c1 < c2.
We shall see that the constant factors can be far less significant in therunning time than the dependence on the input size n. Where merge sort has a factor of lg n inits running time, insertion sort has a factor of n, which is much larger. Although insertion sortis usually faster than merge sort for small input sizes, once the input size n becomes largeenough, merge sort's advantage of lg n vs. n will more than compensate for the difference inconstant factors.
No matter how much smaller c1 is than c2, there will always be a crossoverpoint beyond which merge sort is faster.For a concrete example, let us pit a faster computer (computer A) running insertion sortagainst a slower computer (computer B) running merge sort. They each must sort an array ofone million numbers. Suppose that computer A executes one billion instructions per secondand computer B executes only ten million instructions per second, so that computer A is 100times faster than computer B in raw computing power. To make the difference even moredramatic, suppose that the world's craftiest programmer codes insertion sort in machinelanguage for computer A, and the resulting code requires 2n2 instructions to sort n numbers.(Here, c1 = 2.) Merge sort, on the other hand, is programmed for computer B by an averageprogrammer using a high-level language with an inefficient compiler, with the resulting codetaking 50n lg n instructions (so that c2 = 50).
To sort one million numbers, computer A takeswhile computer B takesBy using an algorithm whose running time grows more slowly, even with a poor compiler,computer B runs 20 times faster than computer A! The advantage of merge sort is even morepronounced when we sort ten million numbers: where insertion sort takes approximately 2.3days, merge sort takes under 20 minutes. In general, as the problem size increases, so does therelative advantage of merge sort.Algorithms and other technologiesThe example above shows that algorithms, like computer hardware, are a technology. Totalsystem performance depends on choosing efficient algorithms as much as on choosing fasthardware.
Just as rapid advances are being made in other computer technologies, they arebeing made in algorithms as well.You might wonder whether algorithms are truly that important on contemporary computers inlight of other advanced technologies, such as••••hardware with high clock rates, pipelining, and superscalar architectures,easy-to-use, intuitive graphical user interfaces (GUIs),object-oriented systems, andlocal-area and wide-area networking.The answer is yes. Although there are some applications that do not explicitly requirealgorithmic content at the application level (e.g., some simple web-based applications), mostalso require a degree of algorithmic content on their own. For example, consider a web-basedservice that determines how to travel from one location to another.
(Several such servicesexisted at the time of this writing.) Its implementation would rely on fast hardware, agraphical user interface, wide-area networking, and also possibly on object orientation.However, it would also require algorithms for certain operations, such as finding routes(probably using a shortest-path algorithm), rendering maps, and interpolating addresses.Moreover, even an application that does not require algorithmic content at the applicationlevel relies heavily upon algorithms. Does the application rely on fast hardware? Thehardware design used algorithms. Does the application rely on graphical user interfaces? Thedesign of any GUI relies on algorithms.
Does the application rely on networking? Routing innetworks relies heavily on algorithms. Was the application written in a language other thanmachine code? Then it was processed by a compiler, interpreter, or assembler, all of whichmake extensive use of algorithms. Algorithms are at the core of most technologies used incontemporary computers.Furthermore, with the ever-increasing capacities of computers, we use them to solve largerproblems than ever before. As we saw in the above comparison between insertion sort andmerge sort, it is at larger problem sizes that the differences in efficiencies between algorithmsbecome particularly prominent.Having a solid base of algorithmic knowledge and technique is one characteristic thatseparates the truly skilled programmers from the novices.
With modern computingtechnology, you can accomplish some tasks without knowing much about algorithms, butwith a good background in algorithms, you can do much, much more.Exercises 1.2-1Give an example of an application that requires algorithmic content at the application level,and discuss the function of the algorithms involved.Exercises 1.2-2Suppose we are comparing implementations of insertion sort and merge sort on the samemachine.
For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lgn steps. For which values of n does insertion sort beat merge sort?Exercises 1.2-3What is the smallest value of n such that an algorithm whose running time is 100n2 runs fasterthan an algorithm whose running time is 2n on the same machine?Problems 1-1: Comparison of running timesFor each function f(n) and time t in the following table, determine the largest size n of aproblem that can be solved in time t, assuming that the algorithm to solve the problem takesf(n) microseconds.1111111second minute hour day month year centurylg nnn lg nn2n32nn!Chapter notesThere are many excellent texts on the general topic of algorithms, including those by Aho,Hopcroft, and Ullman [5, 6], Baase and Van Gelder [26], Brassard and Bratley [46, 47],Goodrich and Tamassia [128], Horowitz, Sahni, and Rajasekaran [158], Kingston [179],Knuth [182, 183, 185], Kozen [193], Manber [210], Mehlhorn [217, 218, 219], Purdom andBrown [252], Reingold, Nievergelt, and Deo [257], Sedgewick [269], Skiena [280], and Wilf[315].
Some of the more practical aspects of algorithm design are discussed by Bentley [39,40] and Gonnet [126]. Surveys of the field of algorithms can also be found in the Handbookof Theoretical Computer Science, Volume A [302] and the CRC Handbook on Algorithmsand Theory of Computation [24]. Overviews of the algorithms used in computational biologycan be found in textbooks by Gusfield [136], Pevzner [240], Setubal and Medinas [272], andWaterman [309].Chapter 2: Getting StartedThis chapter will familiarize you with the framework we shall use throughout the book tothink about the design and analysis of algorithms.
It is self-contained, but it does includeseveral references to material that will be introduced in Chapters 3 and 4. (It also containsseveral summations, which Appendix A shows how to solve.)We begin by examining the insertion sort algorithm to solve the sorting problem introduced inChapter 1. We define a "pseudocode" that should be familiar to readers who have donecomputer programming and use it to show how we shall specify our algorithms. Havingspecified the algorithm, we then argue that it correctly sorts and we analyze its running time.The analysis introduces a notation that focuses on how that time increases with the number ofitems to be sorted.
Following our discussion of insertion sort, we introduce the divide-andconquer approach to the design of algorithms and use it to develop an algorithm called mergesort. We end with an analysis of merge sort's running time.2.1 Insertion sortOur first algorithm, insertion sort, solves the sorting problem introduced in Chapter 1:••Input: A sequence of n numbers a1, a2, .
. .,an .Output: A permutation (reordering)of the input sequence such that.The numbers that we wish to sort are also known as the keys.In this book, we shall typically describe algorithms as programs written in a pseudocode thatis similar in many respects to C, Pascal, or Java. If you have been introduced to any of theselanguages, you should have little trouble reading our algorithms.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
