Анализ временной сложности трех различных алгоритмов Фибоначчи.

Ниже приведен один из наиболее типичных алгоритмов, предлагаемых начинающим студентам: вывести первые n чисел в последовательности Фибоначчи, в которой каждое число является суммой двух предыдущих чисел.

Первые 10 чисел Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Теперь, если бы вы реализовали алгоритм для выполнения задачи вычисления чисел Фибоначчи, у вас было бы множество возможных подходов. «Наивный» — это простой рекурсивный алгоритм:

Какова временная сложность этого алгоритма? Чтобы ответить правильно, мы должны понимать, что делает эта программа: при произвольном n она проверяет, равно ли n = 0, возвращая 0, или n = 1, возвращая 1 (первое число Фибоначчи). В противном случае возвращается f(n-1) + f(n-2), что точно соответствует определению числа Фибоначчи: сумма двух предыдущих чисел в последовательности. Это означает, что функция f будет вызывать сама себя до тех пор, пока n = 0 или n = 1. Например, для n = 4:

f(4) вернет f(3) + f(2)

f(3) вернет f(2) + f(1)

f(2) вернет f(1) + f(0)

f(1) вернет 1

f(0) вернет 0, тогда:

f(2) = f(1) + f(0) = 1,

f(3) = f(2) + f(1) = 1 + 1 = 2,

f(4) = f(3) + f(2) = 2 + 1 = 3, что действительно является четвертым числом в последовательности Фибоначчи.

Вернемся к временной сложности этого алгоритма. Как легко заметить, если n = 1 или n = 0, функция f каждый раз будет вызывать себя дважды. Визуальный подход – это:

Поэтому разумно ожидать экспоненциального времени выполнения для этого алгоритма. Верхняя граница времени выполнения составляет O(2ⁿ). Вообще-то можно найти и более точную оценку времени выполнения, что обсуждается в следующей статье Эмили Маршалл: https://www.baeldung.com/cs/fibonacci-computational-complexity

Теперь, если вы посмотрите на изображение выше, вы заметите, что многие вычисления выполняются более одного раза, например, f(2). Что, если бы мы могли разработать алгоритм, который мог бы запоминать уже выполненные вычисления, уменьшая наше дерево рекурсии?

Такой подход известен как мемоизация, поскольку мы найдем способ регистрировать ранее выполненные вычисления, избегая повторения.

Хотя мы по-прежнему используем рекурсию, на этот раз, если мы уже вычислили определенное число Фибоначчи, функция напрямую возвращает это значение, вместо того, чтобы делать дополнительные вызовы рекурсии.

Для этого конкретного алгоритма временная сложность составляет O (n). Это потому, что теперь каждый вызов функции не приводит к еще двум вызовам. Возьмите f(4) в качестве примера. Сначала он вычисляет f(2) и f(3), сохраняя их значения в векторе lst. Когда он возвращается к функции и вызывает f(2), значение уже вычислено.

Есть еще одна возможность, которая полностью исключает рекурсию. Это подход снизу вверх. Давайте взглянем:

На этот раз нам вообще не нужно было делать рекурсивный вызов: функция f получает вектор (мы используем векторный класс C++ STL), который был инициализирован 0 по индексу 0 и 1 по индексу 1. Для любого n, все, что осталось сделать, это суммировать элементы вектора, пока мы не достигнем нужной позиции n.

Опять же, временная сложность равна O(n). Это легко увидеть, поскольку функция просто перебирает вектор, суммируя каждую пару соседних значений.

Я надеюсь, что эта короткая статья побудила вас к дальнейшему изучению сложности алгоритмов и времени их выполнения, а также к невероятному появлению динамического программирования.