The most Important factor in a certain algorithm
I have read many posts I searched on these forums about algorithms, and had a look at some materials about how to analyze some simple algorithms. I however still do not understand how I can determine the most important factor in a certain algorithm. Especially in case there are many a loop and many different computations in those loops. How will I know Which one I have to choose among them then ?
Anyone please help me ?
Thanks a lot,
Re: The most Important factor in a certain algorithm
Quote:
Originally posted by Charleston I however still do not understand how I can determine the most important factor in a certain algorithm. Especially in case there are many a loop and many different computations in those loops. How will I know Which one I have to choose among them then ?
Conceptually, for many cases it's not that hard. You start off by analyzing the program flow. In case there are recursive function calls, you need to (at least in your mind or on paper) unroll the recursion and rewrite it as a loop.
Then, you have to quantify your input. Which parameters influence how the algorithm scales? In some cases, it's easy, and in other cases a bit harder. Most of the time this is only one number, say N, but sometimes it also depends on other numbers. For the classic sorting algorithm example, N would be the number of elements in the array.
Then when you code structure only consist of loops and ifs, you start off from the outside. How many times is the external loop executed (as a function of N). Then, check how many times the inner loops are executed. This does require either intuition (and experience) or a very careful analysis.
Finally, you multiply the inner loop's complexity by the outer loop's complexity (more, if there are more nested loops).