My confusion comes from the following piece of code:
memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
I used to think that the time complexity for this code is O(n) due to its
use of memoization.
However, I was told recently that in Python, dictionary is a special kind of
array and to append new element to it or to resize it, it is in fact
internally inplemented by creating another array and copying the old one to
it and append a new one.
Therefore, for "memo[n] = fib_memo(n-1) + fib_memo(n-2)", the time it taks
is not at all constant. The larger the n grows, the more time this statement
takes.
Can anybody here familiar with the internal mechanism of python confirm
this?
--
http://mail.python.org/mailman/listinfo/python-list
