Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 7
Текст из файла (страница 7)
In the case of INSERTION-SORT, this time isafter assigning 2 to the variable j but before the first test of whether j ≤ length[A].[2]In real programming languages, it is generally not advisable to use indentation alone toindicate block structure, since levels of indentation are hard to determine when code is splitacross pages.[3]Most block-structured languages have equivalent constructs, though the exact syntax maydiffer from that of Pascal.2.2 Analyzing algorithmsAnalyzing an algorithm has come to mean predicting the resources that the algorithmrequires. Occasionally, resources such as memory, communication bandwidth, or computerhardware are of primary concern, but most often it is computational time that we want tomeasure. Generally, by analyzing several candidate algorithms for a problem, a most efficientone can be easily identified.
Such analysis may indicate more than one viable candidate, butseveral inferior algorithms are usually discarded in the process.Before we can analyze an algorithm, we must have a model of the implementation technologythat will be used, including a model for the resources of that technology and their costs.
Formost of this book, we shall assume a generic one-processor, random-access machine (RAM)model of computation as our implementation technology and understand that our algorithmswill be implemented as computer programs. In the RAM model, instructions are executed oneafter another, with no concurrent operations. In later chapters, however, we shall haveoccasion to investigate models for digital hardware.Strictly speaking, one should precisely define the instructions of the RAM model and theircosts. To do so, however, would be tedious and would yield little insight into algorithmdesign and analysis. Yet we must be careful not to abuse the RAM model. For example, whatif a RAM had an instruction that sorts? Then we could sort in just one instruction. Such aRAM would be unrealistic, since real computers do not have such instructions.
Our guide,therefore, is how real computers are designed. The RAM model contains instructionscommonly found in real computers: arithmetic (add, subtract, multiply, divide, remainder,floor, ceiling), data movement (load, store, copy), and control (conditional and unconditionalbranch, subroutine call and return).
Each such instruction takes a constant amount of time.The data types in the RAM model are integer and floating point. Although we typically do notconcern ourselves with precision in this book, in some applications precision is crucial. Wealso assume a limit on the size of each word of data. For example, when working with inputsof size n, we typically assume that integers are represented by c lg n bits for some constant c ≥1. We require c ≥ 1 so that each word can hold the value of n, enabling us to index theindividual input elements, and we restrict c to be a constant so that the word size does notgrow arbitrarily.
(If the word size could grow arbitrarily, we could store huge amounts of datain one word and operate on it all in constant time-clearly an unrealistic scenario.)Real computers contain instructions not listed above, and such instructions represent a grayarea in the RAM model. For example, is exponentiation a constant-time instruction? In thegeneral case, no; it takes several instructions to compute xy when x and y are real numbers. Inrestricted situations, however, exponentiation is a constant-time operation. Many computershave a "shift left" instruction, which in constant time shifts the bits of an integer by kpositions to the left. In most computers, shifting the bits of an integer by one position to theleft is equivalent to multiplication by 2.
Shifting the bits by k positions to the left is equivalentto multiplication by 2k. Therefore, such computers can compute 2k in one constant-timeinstruction by shifting the integer 1 by k positions to the left, as long as k is no more than thenumber of bits in a computer word. We will endeavor to avoid such gray areas in the RAMmodel, but we will treat computation of 2k as a constant-time operation when k is a smallenough positive integer.In the RAM model, we do not attempt to model the memory hierarchy that is common incontemporary computers.
That is, we do not model caches or virtual memory (which is mostoften implemented with demand paging). Several computational models attempt to accountfor memory-hierarchy effects, which are sometimes significant in real programs on realmachines. A handful of problems in this book examine memory-hierarchy effects, but for themost part, the analyses in this book will not consider them. Models that include the memoryhierarchy are quite a bit more complex than the RAM model, so that they can be difficult towork with. Moreover, RAM-model analyses are usually excellent predictors of performanceon actual machines.Analyzing even a simple algorithm in the RAM model can be a challenge.
The mathematicaltools required may include combinatorics, probability theory, algebraic dexterity, and theability to identify the most significant terms in a formula. Because the behavior of analgorithm may be different for each possible input, we need a means for summarizing thatbehavior in simple, easily understood formulas.Even though we typically select only one machine model to analyze a given algorithm, westill face many choices in deciding how to express our analysis. We would like a way that issimple to write and manipulate, shows the important characteristics of an algorithm's resourcerequirements, and suppresses tedious details.Analysis of insertion sortThe time taken by the INSERTION-SORT procedure depends on the input: sorting a thousandnumbers takes longer than sorting three numbers.
Moreover, INSERTION-SORT can takedifferent amounts of time to sort two input sequences of the same size depending on hownearly sorted they already are. In general, the time taken by an algorithm grows with the sizeof the input, so it is traditional to describe the running time of a program as a function of thesize of its input.
To do so, we need to define the terms "running time" and "size of input"more carefully.The best notion for input size depends on the problem being studied. For many problems,such as sorting or computing discrete Fourier transforms, the most natural measure is thenumber of items in the input-for example, the array size n for sorting. For many otherproblems, such as multiplying two integers, the best measure of input size is the total numberof bits needed to represent the input in ordinary binary notation. Sometimes, it is moreappropriate to describe the size of the input with two numbers rather than one.
For instance, ifthe input to an algorithm is a graph, the input size can be described by the numbers of verticesand edges in the graph. We shall indicate which input size measure is being used with eachproblem we study.The running time of an algorithm on a particular input is the number of primitive operationsor "steps" executed. It is convenient to define the notion of step so that it is as machineindependent as possible. For the moment, let us adopt the following view. A constant amountof time is required to execute each line of our pseudocode.
One line may take a differentamount of time than another line, but we shall assume that each execution of the ith line takestime ci , where ci is a constant. This viewpoint is in keeping with the RAM model, and it alsoreflects how the pseudocode would be implemented on most actual computers.[4]In the following discussion, our expression for the running time of INSERTION-SORT willevolve from a messy formula that uses all the statement costs ci to a much simpler notationthat is more concise and more easily manipulated.
This simpler notation will also make it easyto determine whether one algorithm is more efficient than another.We start by presenting the INSERTION-SORT procedure with the time "cost" of eachstatement and the number of times each statement is executed. For each j = 2, 3, . . . , n, wheren = length[A], we let tj be the number of times the while loop test in line 5 is executed for thatvalue of j. When a for or while loop exits in the usual way (i.e., due to the test in the loopheader), the test is executed one time more than the loop body. We assume that comments arenot executable statements, and so they take no time.INSERTION-SORT(A)1 for j ← 2 to length[A]2do key ← A[j]345678▹ Insert A[j] into the sortedsequence A[1j - 1].i ← j - 1while i > 0 and A[i] > keydo A[i + 1] ← A[i]i ← i - 1A[i + 1] ← keycostc1c2timesnn - 10c4c5c6c7c8n - 1n - 1n - 1The running time of the algorithm is the sum of running times for each statement executed; astatement that takes ci steps to execute and is executed n times will contribute cin to the totalrunning time.[5] To compute T(n), the running time of INSERTION-SORT, we sum theproducts of the cost and times columns, obtainingEven for inputs of a given size, an algorithm's running time may depend on which input ofthat size is given.
For example, in INSERTION-SORT, the best case occurs if the array isalready sorted. For each j = 2, 3, . . . , n, we then find that A[i] ≤ key in line 5 when i has itsinitial value of j - 1. Thus tj = 1 for j = 2, 3, . . . , n, and the best-case running time isT(n) = c1n + c2(n - 1) + c4(n - 1) + c5(n - 1) + c8(n - 1)= (c1 + c2 + c4 + c5 + c8)n - (c2+ c4 + c5 + c8).This running time can be expressed as an + b for constants a and b that depend on thestatement costs ci ; it is thus a linear function of n.If the array is in reverse sorted order-that is, in decreasing order-the worst case results. Wemust compare each element A[j] with each element in the entire sorted subarray A[1 j - 1],and so tj = j for j = 2, 3, . .
. , n. Noting thatand(see Appendix A for a review of how to solve these summations), we find that in the worstcase, the running time of INSERTION-SORT isThis worst-case running time can be expressed as an2 + bn + c for constants a, b, and c thatagain depend on the statement costs ci ; it is thus a quadratic function of n.Typically, as in insertion sort, the running time of an algorithm is fixed for a given input,although in later chapters we shall see some interesting "randomized" algorithms whosebehavior can vary even for a fixed input.Worst-case and average-case analysisIn our analysis of insertion sort, we looked at both the best case, in which the input array wasalready sorted, and the worst case, in which the input array was reverse sorted.
For theremainder of this book, though, we shall usually concentrate on finding only the worst-caserunning time, that is, the longest running time for any input of size n. We give three reasonsfor this orientation.•••The worst-case running time of an algorithm is an upper bound on the running time forany input. Knowing it gives us a guarantee that the algorithm will never take anylonger. We need not make some educated guess about the running time and hope thatit never gets much worse.For some algorithms, the worst case occurs fairly often.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
