Thuật toán Algorithms (Phần 3)

Tham khảo tài liệu thuật toán algorithms (phần 3), khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Thuật toán Algorithms (Phần 3)expected to take on “typical” input data, and in the worst case, the amountof time a program would take on the worst possible input configuration. Many of the algorithms in this book are very well understood, to the pointthat accurate mathematical formulas are known for the average- and worst-case running time. Such formulas are developed first by carefully studyingthe program, to find the running time in terms of fundamental mathematicalquantities and then doing a mathematical analysis of the quantities involved. For some algorithms, it is easy to hgure out the running time. For ex-ample, the brute-force algorithm above obviously requires min(u, VU)-gcd(u, V)iterations of the while loop, and this quantity dominates the running time ifthe inputs are not small, since all the other statements are executed either0 or 1 times. For other algorithms, a substantial amount of analysis is in-volved. For example, the running time of the recursive Euclidean algorithmobviously depends on the “overhead” required for each recursive call (whichcan be determined only through detailed1 knowledge of the programming en-vironment being used) as well as the number of such calls made (which canbe determined only through extremely sophisticated mathematical analysis). Several important factors go into this analysis which are somewhat out-side a given programmer’s domain of influence. First, Pascal programs aretranslated into machine code for a given computer, and it can be a challengingtask to figure out exactly how long even one Pascal statement might take toexecute (especially in an environment where resources are being shared, sothat even the same program could have varying performance characteristics).Second, many programs are extremely sensitive to their input data, and per-formance might fluctuate wildly depending on the input. The average casemight be a mathematical fiction that is not representative of the actual dataon which the program is being used, and the worst case might be a bizarreconstruction that would never occur in practice. Third, many programs ofinterest are not well understood, and specific mathematical results may notbe available. Finally, it is often the case that programs are not comparable atall: one runs much more efficiently on one particular kind of input, the otherruns efficiently under other circumstances. With these caveats in mind, we’ll use rough estimates for the runningtime of our programs for purposes of classification, secure in the knowledgethat a fuller analysis can be done for important programs when necessary.Such rough estimates are quite often easy to obtain via the old programmingsaw “90% of the time is spent in 10% of the code.” (This has been quoted inthe past for many different values of “go%.“) The first step in getting a rough estimate of the running time of a programis to identify the inner loop. Which instructions in the program are executedmost often? Generally, it is only a few instructions, nested deep within the CHAPTER 1control structure of a program, that absorb all of the machine cycles. It isalways worthwhile for the programmer to be aware of the inner loop, just tobe sure that unnecessary expensive instructions are not put there. Second, some analysis is necessary to estimate how many times the innerloop is iterated. It would be beyond the scope of this book to describe themathematical mechanisms which are used in such analyses, but fortunatelythe running times many programs fall into one of a few distinct classes. Whenpossible, we’ll give a rough description of the analysis of the programs, but itwill often be necessary merely to refer to the literature. (Specific referencesare given at the end of each major section of the book.) For example, theresults of a sophisticated mathematical argument show that the number ofrecursive steps in Euclid’s algorithm when u is chosen at random less than v isapproximately ((12 In 2)/7r2) 1 n TJ. Often, the results of a mathematical analysisare not exact, but approximate in a precise technical sense: the result mightbe an expression consisting of a sequence of decreasing terms. Just as we aremost concerned with the inner loop of a program, we are most concerned withthe leading term (the largest term) of a mathematical expression. As mentioned above, most algorithms have a primary parameter N,usually the number of data items to be processed, which affects the runningtime most significantly. The parameter N might be the degree of a polyno-mial, the size of a file to be sorted or searched, the number of nodes in agraph, etc. Virtually all of the algorithms in this book have running timeproportional to one of the following functions:1 Most instructions of most programs are executed once or at most ...