Почему числа Фибоначчи важны в информатике?

числа Фибоначчи имеют все виды действительно хороших математических свойств, которые делают их превосходными в информатике. Вот несколько:

1. они растут экспоненциально быстро. одна интересная структура данных, в которой появляется ряд Фибоначчи,-это дерево AVL, форма самобалансирующегося двоичного дерева. Интуиция за этим деревом заключается в том, что каждый узел поддерживает коэффициент баланса, так что высоты левого и правого поддерева отличаются не более чем на один. Из-за этого вы можете думать о минимальном количестве узлов, необходимых для получения дерева AVL высоты h, определяется повторением, которое выглядит как N(h + 2) ~= N(h) + N(h + 1), что очень похоже на ряд Фибоначчи. Если вы разработаете математику, вы можете показать, что количество узлов, необходимых для получения дерева AVL высотой h, равно F(h + 2) - 1. Поскольку ряд Фибоначчи растет экспоненциально быстро, это означает, что высота дерева AVL является не более логарифмической по числу узлов, что дает вам время поиска O(lg n) мы знаем и любим о сбалансированных бинарных деревьях. На самом деле, если вы можете связать размер некоторой структуры с числом Фибоначчи, вы, вероятно, получите время выполнения O(lg n) на некоторой операции. Это реальная причина того, что кучи Фибоначчи называются кучами Фибоначчи - доказательство того, что количество куч после удаления min включает в себя ограничение количества узлов, которые вы можете иметь на определенной глубине с числом Фибоначчи.
2. любое число может быть записано как сумма уникальные числа Фибоначчи. это свойство чисел Фибоначчи имеет решающее значение для того, чтобы поиск Фибоначчи работал вообще; если вы не можете сложить уникальные числа Фибоначчи в любое возможное число, этот поиск не будет работать. Сравните это с большим количеством других серий, как 3ⁿ или каталонские числа. Это также частично объясняет, почему многие алгоритмы, такие как степени двух, я думаю.
3. числа Фибоначчи эффективно вычислимы. в тот факт, что ряд может быть сгенерирован чрезвычайно эффективно (вы можете получить первые N членов в O(n) или любой произвольный член в O(lg n)), тогда многие алгоритмы, которые их используют, не будут практичными. Генерация каталонских чисел довольно сложна в вычислительном отношении, IIRC. Кроме того, числа Фибоначчи имеют хорошее свойство, где, учитывая любые два последовательных числа Фибоначчи, скажем F(k) и F (k + 1), мы можем легко вычислить следующее или предыдущее число Фибоначчи, добавив два значения (F(k) + F(k + 1) = F (k + 2)) или вычитание их(F(k + 1) - F(k) = F (k - 1)). Это свойство используется в нескольких алгоритмах, в сочетании со свойством (2), чтобы разбить числа на сумму чисел Фибоначчи. Например, поиск Фибоначчи используется для поиска значений в памяти, в то время как аналогичный алгоритм может быть использован для быстрого и эффективного расчета логарифмов.
4. они педагогически полезно. обучение рекурсии сложно, и ряд Фибоначчи отличный способ представить его. Можно говорить о прямой рекурсии, о мемоизации, или о динамическом программировании при внедрении серии. Кроме того, удивительный закрытая форма для чисел Фибоначчи часто преподается как упражнение в индукции или в анализе бесконечных рядов и связанных с ними матричное уравнение для чисел Фибоначчи обычно вводится в линейной алгебре в качестве мотивации за собственные векторы и собственные значения. Я думаю, что это это одна из причин того, что они так громко выступают на вводных занятиях.

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