tailieunhanh - 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ả | PREVIEW 13 expected to take on typical input data and in the worst case the amount of time a program would take on the worst possible input configuration. Many of the algorithms in this book are very well understood to the point that accurate mathematical formulas are known for the average- and case running time. Such formulas are developed first by carefully studying the program to find the running time in terms of fundamental mathematical quantities and then doing a mathematical analysis of the quantities involved. For some algorithms it is easy to out the running time. For example the brute-force algorithm above obviously requires iterations of the while loop and this quantity dominates the running time if the inputs are not small since all the other statements are executed either 0 or 1 times. For other algorithms a substantial amount of analysis is involved. For example the running time of the recursive Euclidean algorithm obviously depends on the overhead required for each recursive call which can be determined only through detailed1 knowledge of the programming environment being used as well as the number of such calls made which can be determined only through extremely sophisticated mathematical analysis . Several important factors go into this analysis which are somewhat outside a given programmer s domain of influence. First Pascal programs are translated into machine code for a given computer and it can be a challenging task to figure out exactly how long even one Pascal statement might take to execute especially in an environment where resources are being shared so that even the same program could have varying performance characteristics . Second many programs are extremely sensitive to their input data and performance might fluctuate wildly depending on the input. The average case might be a mathematical fiction that is not representative of the actual data on which the program is being used and the worst case might be a bizarre construction that would