Windson Yang <wiwind...@gmail.com> writes: > 'I'm just running them in succession and seeing how long they'. The full > code looks like this, this is only an example.py here. and I run 'time > python3 example.py' for each function. > > def fib_dp(n): > dp = [0] * (n+1) > if n <= 1: > return n > dp[0], dp[1] = 0, 1 > for i in range(2, n+1): > dp[i] = dp[i-1] + dp[i-2] > return dp[-1] ... > # run the function only once > # fib_dp(400000) # took more than 60s > # fib_dp2(400000) # took about 2s
Figure out how much memory fib_dp is holding on to right before it returns the answer. fib(400000) is a _big_ number! And so is fib(399999), and fib(399998), and fib(399997), etc. By the time you're done, you're holding on to quite a huge pile of storage here. Depending on how much physical memory you have, you much actually be swapping before you're done. -- Alan Bawden -- https://mail.python.org/mailman/listinfo/python-list
