Числа Фибоначчи

Числа Фибоначчи задаются как F(0)=0, F(1)=1 и F(n)=F(n−1)+F(n−2). Наивная рекурсия считает их за экспоненциальное время O(2^n) из-за повторов; итеративный подход или мемоизация дают O(n).

Сложность: время O(n), память O(1) при хранении двух последних значений. Существует и метод за O(log n) через возведение матрицы в степень.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib(i) for i in range(8)])  # [0,1,1,2,3,5,8,13]