Skip to content

Instantly share code, notes, and snippets.

@RobGThai
Last active October 23, 2021 15:04
Show Gist options
  • Save RobGThai/61bcc5e92cb4dce0aaa22c9775bb4b68 to your computer and use it in GitHub Desktop.
Save RobGThai/61bcc5e92cb4dce0aaa22c9775bb4b68 to your computer and use it in GitHub Desktop.
Fibonacci implementations.
class Solution:
def fib(self, n: int) -> int:
# 0 1 2 3 4 5 6
# 0 1 1 2 3 5 8
#return self.fib_r(n)
return self.fib_a(n)
def fib_a(self, n:int) -> int:
# Time Complexity: O(n)
# Space Complexity: O(1)
if n == 0:
return 0
elif n == 1:
return 1
prevF = 0
prevL = 1
i = 2
while i <= n:
x = prevF + prevL
prevF, prevL = prevL, x
i += 1
return prevL
def fib_slow(self, n: int) -> int:
# Time Complexity: O(n)
# Space Complexity: O(n * n)
if n == 0:
return 0
elif n == 1:
return 1
return self.fib_r(n - 1) + self.fib_r(n - 2)
def fib_r(self, n: int) -> int:
# Time Complexity: O(n)
# Space Complexity: O(n)
if n == 0:
return 0
elif n == 1:
return 1
def _fib(n: int) -> [int]:
if n == 1:
return 0, 1
a, b = _fib(n - 1)
return b, (a + b)
a, b = _fib(n)
return b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment