Ряд Фибоначчи представляет собой последовательность чисел, в которой каждое число представляет собой сумму двух предыдущих, обычно начиная с 0 и 1. В этой статье блога мы углубимся в различные итеративные методы расчета ряда Фибоначчи и обсудим их временные сложности. Мы предоставим разговорные объяснения и примеры кода, которые помогут вам лучше понять каждый метод.

Метод 1: наивная итерация
Самый простой подход к итеративному вычислению чисел Фибоначчи — использование цикла. Мы начинаем с первых двух чисел ряда (0 и 1) и итеративно вычисляем следующие числа, пока не достигнем желаемой позиции.

def fibonacci_iterative(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        prev, curr = 0, 1
        for _ in range(3, n + 1):
            prev, curr = curr, prev + curr
        return curr

Временная сложность этого метода составляет O(n), поскольку нам нужно повторить n-2 раза, чтобы вычислить n-е число Фибоначчи.

Метод 2: Мемоизация
Мемоизация — это метод оптимизации, который сохраняет результаты дорогостоящих вызовов функций и возвращает кэшированный результат, когда те же входные данные повторяются. В контексте Фибоначчи мы можем использовать мемоизацию, чтобы избежать избыточных вычислений.

def fibonacci_iterative_memo(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        fib = [0, 1]
        for i in range(3, n + 1):
            fib.append(fib[-1] + fib[-2])
            fib = fib[-2:]
        return fib[-1]

Временная сложность этого метода также равна O(n), но она может быть быстрее, чем метод простой итерации для больших значений n, поскольку мы избегаем избыточных вычислений.

Метод 3: возведение матрицы в степень
Другой эффективный итеративный подход к вычислению чисел Фибоначчи — использование возведения матрицы в степень. Мы можем представить ряд Фибоначчи в виде матрицы и использовать свойства возведения матрицы в степень для вычисления желаемого числа Фибоначчи.

import numpy as np
def fibonacci_iterative_matrix(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        fib_matrix = np.array([[1, 1], [1, 0]], dtype=object)
        result = np.array([[1, 0]], dtype=object)
        for _ in range(3, n + 1):
            result = np.matmul(result, fib_matrix)
        return result[0][1]

Временная сложность этого метода составляет O(log n), поскольку мы выполняем log n умножения матриц.

В этой статье мы исследовали три различных итерационных метода расчета ряда Фибоначчи: наивная итерация, мемоизация и возведение матрицы в степень. Мы предоставили примеры кода и объяснили временные сложности каждого метода. В зависимости от значения n и конкретных требований вашего приложения вы можете выбрать наиболее подходящий метод итеративного расчета ряда Фибоначчи.