If you were given a task to compute the nth Fibonacci number, how would you do it?
You would go straight away and write a recursive function right?
public static int getNumberRecurse(int n) { if (n == 0 | n == 1) { return 1; } else { return getNumberRecurse(n - 1) + getNumberRecurse(n - 2); } }
elapsed for n=30: 31 ms
elapsed for n=40: 3016 ms
Well think again. Because there might be a better way of doing it.
public static int getNumberLoop(int n) {
if (n == 0 | n == 1) {
return 1;
} else {
int[] fib = new int[n + 1];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
}
[/sourcecode]
elapsed for n=100000: 31 ms
If we compare the elapsed time (in ms) between the two functions, we can clearly see which one is better.
Anyway, I've found an invaluable book called Algorithms from where I got the example above.
I know a lot of programmers (myself included) who are easily satisfied with a workable solution rather than an efficient one.
I hope someday (with enough time and practice) I can be an expert on this topic too.