Thank you, Chris. I tried your suggestions. I don't think that is the reason, fib_dp_look() and fib_dp_set() which also allocation a big list can return in 2s.
Chris Angelico <ros...@gmail.com> 于2019年8月25日周日 上午11:27写道： > 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 > -- https://mail.python.org/mailman/listinfo/python-list
