Naive, recursive Fibonacci is exponential in time and constant in space.
Memoized Fibonacci is linear in time in the worst case, but nearly constant in the case of recomputing a previous value. It's linear in space requirements.
Automatically iteratized Fibonacci is linear in time and constant in space.
The last two can be automatically created from the first. I want to be able to tell the compiler that I want it to replace my Fibonacci with one of the more efficient ones.
Advantages:
- My original implementation of Fibonacci is clear, simple, and minimal. It follows very closely the standard mathematical formulation. It remains clear.
- Only one more line of code to go from O(2^n) -> O(n). Little extra investment.
- I can switch between optimizations easily if I need to.
Disadvantages:
- Complexity of having to learn what optimizations are possible.
Note: You still have complete control over your code. You can choose not to optimize. You can always optimize it by hand.
Optimize Algorithm
I think we're all in agreement about that.
Naive, recursive Fibonacci is exponential in time and constant in space.
Memoized Fibonacci is linear in time in the worst case, but nearly constant in the case of recomputing a previous value. It's linear in space requirements.
Automatically iteratized Fibonacci is linear in time and constant in space.
The last two can be automatically created from the first. I want to be able to tell the compiler that I want it to replace my Fibonacci with one of the more efficient ones.
Advantages:
- My original implementation of Fibonacci is clear, simple, and minimal. It follows very closely the standard mathematical formulation. It remains clear.
- Only one more line of code to go from O(2^n) -> O(n). Little extra investment.
- I can switch between optimizations easily if I need to.
Disadvantages:
- Complexity of having to learn what optimizations are possible.
Note: You still have complete control over your code. You can choose not to optimize. You can always optimize it by hand.