Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
when the code take order of nlog(n) and n^3?
and
Is there any tutorials about analysis of algorithms in this site?
because I need a nice paper to study it .
1 reply to this topic
Back to top|
|
|
#2
Posted 27 July 2010 - 01:48 AM
zoranh
-
- Members
-
- 207 posts
Programming Professional
Before links I'll give you a short hint of algorithm complexity analysis which you won't find in regular literature.
Asymptotic complexity of algorithm is best calculated in this way. Suppose that you have a branching instruction in code (if-then-else statement, for loop, while loop, whatever), and that branch is reached n times. You analyze how many times execution goes via one branch and how many times the other branch. Mostly often, that would be probabilities of entering one branch P1 and another branch P2. Now suppose that number of operations executed in branch 1 is B1 and number of operations in branch 2 is B2. Then total number of operations performed is n*P1*B1+n*P2*B2. Now it remains to calculate n, to calculate probabilities P1 and P2 and to perform the analysis of branches, which means that you have broken the problem into several smaller problems. You keep doing this until all B variables are expressed as functions of n, and finally just clear the formula, remove smaller exponents and you're done.
This method boils down to applying Kirchhoff's laws to algorithm. (It would be better for you to know Ohm's law before doing this part.) You can apply Kirchhoff's law to algorithm by first drawing the algorithm as simple if-then-else branches and plain instructions (i.e. convert all loops to simple branching). Then you would have to calculate branching probabilities for each IF statement. Finally you would end up with a system of linear equations. Once you solve it, you'll get the exact formula specifying average number of operations performed by the algorithm.
And now the references:
Asymptotic complexity of algorithm is best calculated in this way. Suppose that you have a branching instruction in code (if-then-else statement, for loop, while loop, whatever), and that branch is reached n times. You analyze how many times execution goes via one branch and how many times the other branch. Mostly often, that would be probabilities of entering one branch P1 and another branch P2. Now suppose that number of operations executed in branch 1 is B1 and number of operations in branch 2 is B2. Then total number of operations performed is n*P1*B1+n*P2*B2. Now it remains to calculate n, to calculate probabilities P1 and P2 and to perform the analysis of branches, which means that you have broken the problem into several smaller problems. You keep doing this until all B variables are expressed as functions of n, and finally just clear the formula, remove smaller exponents and you're done.
This method boils down to applying Kirchhoff's laws to algorithm. (It would be better for you to know Ohm's law before doing this part.) You can apply Kirchhoff's law to algorithm by first drawing the algorithm as simple if-then-else branches and plain instructions (i.e. convert all loops to simple branching). Then you would have to calculate branching probabilities for each IF statement. Finally you would end up with a system of linear equations. Once you solve it, you'll get the exact formula specifying average number of operations performed by the algorithm.
And now the references:
- Learning example of O(N logN) algorithm - Heapsort algorithm
- Learning example of O(N^3) algorithm - Floyd-Warshall algorithm
- Kirchhoff's law
- Ohm's law
- Asymptotic notation
- Theory of algorithms - Donald E. Knuth, The Art of Computer Programming 1-3
