Created
December 23, 2014 18:03
-
-
Save mark-adams/cdced8cdcc88058b1e5f to your computer and use it in GitHub Desktop.
Fibonacci functions: An Overview of Algorithmic Complexity
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # This guy runs in linear O(n) time. That is good but its somewhat complex | |
| def fib(n): | |
| if n == 0 or n == 1: # 1 | |
| return 1 | |
| lastNum = 1 # 1 | |
| currentNum = 1 # 1 | |
| idx = 1 # 1 | |
| for i in range(n - 1): # 1 | |
| newNum = lastNum + currentNum # n - 1 | |
| lastNum = currentNum # n - 1 | |
| currentNum = newNum # n - 1 | |
| return currentNum # 1 | |
| # This guy is recursive which looks pretty but executes in factorial O(n!). Yikes! | |
| def fib_2(n): | |
| """Get the nth fibonacci number""" | |
| if n == 0 or n == 1: # 1 | |
| return 1 | |
| return fib_2(n - 1) + fib_2(n - 2) # 1 | |
| def memoize(func): | |
| cache = {} | |
| def memoized(*args): | |
| if args in cache: | |
| return cache[args] | |
| result = func(*args) | |
| cache[args] = result | |
| return result | |
| return memoized | |
| # Memoization cuts this down to O(n) time. Nice!!! | |
| fib_3 = memoize(fib_2) | |
| print(fib(10)) | |
| print(fib_2(10)) | |
| print(fib_3(10)) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment