On Sun, Aug 25, 2019 at 12:56 PM Windson Yang <wiwind...@gmail.com> wrote: > > I have two functions to calculate Fibonacci numbers. fib_dp use a list to > store the calculated number. fib_dp2 just use two variables. > > def fib_dp(n): > if n <= 1: > return n > dp = [0] * (n+1) > dp[0], dp[1] = 0, 1 > for i in range(2, n+1): > dp[i] = dp[i-1] + dp[i-2] > return dp[-1] > > def fib_dp2(n): > if n <= 1: > return n > pre, now = 0, 1 > for i in range(2, (n+1)): > pre, now = now, pre+now > return now > > Theoretically, both of their time complexity should be O(n). However, when > the input n is so big (like 400000), fib_dp2(400000) can calculate it in 2s > but fib_dp(400000) takes *more than 60s* (python3.7.3 and macOS 10.14.6). > Why?
Memory allocation can take a long time. Try grabbing the line initializing dp and slapping that into the body of dp2, and then compare their times; that might make all the difference. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
