Analysis of Algorithms
As people gain experience using computers, they use them to solve difficult problems or to process large amounts of data and are invariably led to questions like these:
- How long will my program take?
- Why does my program run out of memory?
For many programs, developing a mathematical model of running time reduces to the following steps:
• Develop an input model, including a definition of the problem size.
• Identify the inner loop.
• Define a cost model that includes operations in the inner loop.
• Determine the frequency of execution of those operations for the given input. Doing so might require mathematical analysis
If a program is defined in terms of multiple methods, we normally consider the methods separately.
Note the "Doubling Ratio" method for determining order of growth of execution times, But remember that this only works if the growth ratio approaches a limit value:
No comments:
Post a Comment