Profile the performance of the memoized version of the Fibonacci function defined in Project 6. The function should count the number of recursive calls. State its computational complexity using big-O notation, and justify your answer.
The fib function header has been modified to include the counter as the second parameter.
Define the Counter class, it should have three methods: __init__, increment, and __str__. When an instance of the Counter class is passed as a parameter, the count property of that instance should be incremented based on the number of recursive calls. The __str__ method should return the count property's value as a string.
-----------------------------------------------------------------------------------
"""
File: fib.py
Project 11.7
Employs memoization to improve the efficiency of recursive Fibonacci.
Counts the calls and displays the results.
"""
class Counter(object):
"""Tracks a count."""
# Define the Counter class here.
def fib(n, counter = None):
"""Fibonacci function with a table for memoization."""
table = {}
def memoizedFib(n):
if n <>
return 1
else:
# Attempt to get value for memoizedFib(n)
# from the table
# If unsuccessful, recurse and add results to
# the table
value = table.get(n, None)
if value: return value
else:
value = memoizedFib(n - 1) + memoizedFib(n - 2)
table[n] = value
return value
return memoizedFib(n)
def main():
"""Tests the function with some powers of 2."""
problemSize = 2
print("%4s%12s" % ("n", "fib(n)"))
for count in range(5):
print("%4d%12d" % (problemSize, fib(problemSize)))
problemSize *= 2
if __name__ == "__main__":
main()