Ruan schreef:
> 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.
That's not correct. Python dictionaries are highly optimized and I
believe the time complexity is amortized constant (i.e. O(1)) for both
insertions and lookups.
--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton
Roel Schroeven
--
http://mail.python.org/mailman/listinfo/python-list
