Fundamentals of the Average Case Analysis of Particular Algorithms (Wiley-Teubner Series in Computer Science): Rainer Kemp

Description

'Analysis of algorithms' is quite important in computer programming, because there are generally several algorithms available for a particular application and we would like to measure and compare the time and storage requirements. Time may be measured by counting steps, statements, or the number of times some given operation is performed; space may be measured by bits, words, or the number of registers and cells required during execution of the algorithm. The analysis usually consists of determining the behaviour of an algorithm in the best case, in the worst case and in the average case. The best (worst) case is characterized by the minimum (maximum) total amount of time or space requirements taken over all inputs of some fixed size. To characterize the average case, it is necessary to define what we mean by the average; in general, we must make some assumptions about the expected characteristics of the inputs of some fixed size. If an input x of size n has the probability px and requires the total amount of time or space kx, then the average case is characterized by the behaviour of the expected value (Appendix A) of the random variable which has th^ value kx with probability px. In most problems we will make the reasonable assumption that each of the inputs of size n is equally likely, but the analysis can also be carried out under other assumptions. To obtain a quantitative indication of how close to the average we may expect the amount of time or storage requirements to be, we will compute further characteristics of the given distribution such as the variance, the standard deviation, the moments about the origin, or the (cumulative) distribution function (Appendix A).

Now an important problem is to compare the time and space requirements of algorithms available for a particular application. Sometimes we want to decide which is best. But this is easier said than done. In many cases we may only compare the time requirements or the storage requirements of two algorithms, because the one algorithm requires less time but more space than the other. Similarly, comparing two algorithms in the best, worst, or average case, the same situation can occur. For example, the sorting algorithm 'Heapsort' is faster than the algorithm 'Quicksort' in the worst case, but not in the average case. Summing up, a comparison of two algorithms should be made only for the time or storage requirements in the best or worst or average case. (Nevertheless, there are other criteria of goodness of algorithms such as the product of time and space requirements or the adaptability to computers.) The classical complexity theory deals with the time and storage requirements of algorithms in the worst case. In practice, there are some objections to the measuring of the goodness of an algorithm by these quantities, although their computation can be an extremely difficult task. If an algorithm requires time or space of order O(f(n)) in the worst case, then the constant in the 0-term can be fantastically large and the result is only of theoretical interest. Furthermore, if the inputs corresponding to the worst case have a probability which tends to zero for large input sizes, then it is hard to see why the goodness of the algorithm is measured by its worst case. Therefore, the importance of the worst case can be reduced by the knowledge of its probability. But the computation of this probability can be rather difficult, unless impossible. In practice, an algorithm requiring time n on the average in 99 per cent of all possible inputs of size n should be preferred to an algorithm for the same problem which needs time n2 in the worst and average case, even though the former algorithm needs time n3 in the worst case.

Study of the behaviour of an algorithm on the average is accompanied by many mathematical calculations; we need to use the results of complex variable theory, number theory, probability theory, discrete mathenutics and combina- combinatorics. The principal techniques involved in the analysis of igorithms consist of counting of certain objects, solving of recurrences, working with finite summations, handling of generating functions and asymptotic evaluating of expressions. The last part of this introductory section is devoted to some simple examples elucidating the above ideas and concepts.

Disclaimer:
Contents of this page are indexed from the Internet. All actions are under your responsability. Email us to report illegal contents or external links and we'll remove them immediately.

Please check the description for download links if any or do a search to find alternative books.

Can't Download?
Please search mirrors if you can't find download links for "Fundamentals of the Average Case Analysis of Particular Algorithms (Wiley-Teubner Series in Computer Science): Rainer Kemp" in "Description" and someone else may update the links. Check the comments when back to find any updates.

Search Mirrors
Maybe some mirror pages will be helpful, search this book at top of this page or click here to find more info.

1. Ebooks list page : 3069
2. Average-Case Analysis of Numerical Problems (Lecture Notes in Mathematics): Klaus Ritter
3. Fundamentals of Wavelets: Theory, Algorithms, and Applications (Wiley Series in Microwave and Optical Engineering)
4. The Design and Analysis of Algorithms (Monographs in Computer Science)
5. The Design and Analysis of Algorithms (Monographs in Computer Science)
6. [share_ebook] The Design and Analysis of Algorithms (Monographs in Computer Science)
7. Dynamic Reconfiguration: Architectures and Algorithms (Series in Computer Science)
8. Mathematics for the Analysis of Algorithms (Progress in Computer Science and Applied Logic (PCS))
9. Knapsack Problems: Algorithms and Computer Implementations (Wiley Interscience Series in Discrete Mathematics and Optimization)
10. Performance Analysis of Queuing and Computer Networks (Chapman & Hall/Crc Computer & Information Science Series)
11. Fundamentals of Computer Organization and Architecture (Wiley Series on Parallel and Distributed Computing)
12. [share_ebook] Performance Analysis of Queuing and Computer Networks (Chapman & Hall/Crc Computer & Information Science Series)
13. New Models and Algorithms (Operations Research/Computer Science Interfaces Series)
14. Colorimetry: Fundamentals and Applications (The Wiley-IS&T Series in Imaging Science and Technology)
15. Data Structures and Algorithms (Addison-Wesley Series in Computer Science and Information Pr)
16. Algorithms for Clustering Data (Prentice Hall Advanced Reference Series : Computer Science)