forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathfib.py
More file actions
89 lines (67 loc) · 1.82 KB
/
fib.py
File metadata and controls
89 lines (67 loc) · 1.82 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
"""
Fibonacci Number
Compute the n-th Fibonacci number using three different approaches:
recursive, list-based DP, and iterative.
Reference: https://en.wikipedia.org/wiki/Fibonacci_number
Complexity:
fib_recursive:
Time: O(2^n)
Space: O(n) (call stack)
fib_list:
Time: O(n)
Space: O(n)
fib_iter:
Time: O(n)
Space: O(1)
"""
from __future__ import annotations
def fib_recursive(n: int) -> int:
"""Compute the n-th Fibonacci number recursively.
Args:
n: Non-negative integer index into the Fibonacci sequence.
Returns:
The n-th Fibonacci number.
Examples:
>>> fib_recursive(10)
55
"""
assert n >= 0, "n must be a positive integer"
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
def fib_list(n: int) -> int:
"""Compute the n-th Fibonacci number using a list-based DP table.
Args:
n: Non-negative integer index into the Fibonacci sequence.
Returns:
The n-th Fibonacci number.
Examples:
>>> fib_list(10)
55
"""
assert n >= 0, "n must be a positive integer"
list_results = [0, 1]
for i in range(2, n + 1):
list_results.append(list_results[i - 1] + list_results[i - 2])
return list_results[n]
def fib_iter(n: int) -> int:
"""Compute the n-th Fibonacci number iteratively with constant space.
Args:
n: Non-negative integer index into the Fibonacci sequence.
Returns:
The n-th Fibonacci number.
Examples:
>>> fib_iter(10)
55
"""
assert n >= 0, "n must be positive integer"
fib_1 = 0
fib_2 = 1
res = 0
if n <= 1:
return n
for _ in range(n - 1):
res = fib_1 + fib_2
fib_1 = fib_2
fib_2 = res
return res