Странная петля Фибоначчи: красота математического начала

0
12307
Добавить в избранное

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

Странная петля Фибоначчи: красота математического начала

Говоря об алгоритмах, нельзя не упомянуть о последовательности Фибоначчи. Она тесно связана с золотым сечением, которое мы снова и снова встречаем в природе, архитектуре, искусстве и даже романе Дэна Брауна. От раковин морских животных до сакральной геометрии, по-видимому, Золотое Сечение закодировано во многих аспектах нашей Вселенной.

Невозможно перечислить все места, где мы можем встретить эту удивительную последовательность, но самое невероятное – она появляется даже внутри самой себя. Рекурсия внутри рекурсии, математическое начало, то, что Хофштадтер мог бы назвать «странной петлей» (strange loop).

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

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

Последовательность была описана в 1202 году Леонардо Фибоначчи. Она начинается с двух единиц, а последующие члены вычисляются путем сложения двух предыдущих. Третий член 1 + 1 = 2, а четвертый 1 + 2 = 3, далее 2 + 3 = 5. Вот первые несколько цифр:

Рекурсивный код выше означает следующее: если n равно 0 или 1, функция вернет единицу, иначе – результат сложения fib(n-1) и fib(n-2), то есть сумму двух предыдущих членов.

Ряд Фибоначчи и золотое сечение

Кроме самой последовательности, Фибоначчи обнаружил ее связь с золотым сечением.

Золотое сечение – иррациональное число. Как и 𝞹 (число Пи), оно имеет бесконечное количество цифр после запятой, которые никогда не образуют повторяющихся шаблонов. Большинство из нас помнят 𝞹 как 3.14, а золотое сечение можно запомнить как 1.618. Буквенное представление этой величины – 𝝓 (фи, Phi).

Если взять n-ный член последовательности Фибоначчи и разделить его на (n-1)-ный, то полученный результат будет приблизительно равен золотому сечению. Чем дальше от начала, тем точнее приближение:

Ряд Фибоначчи как алгоритмическая сложность

Вероятно, вы знаете, что рекурсивный код работает медленно. А знаете ли вы, что он работает медленно таким образом, который тесно связан с числом 𝝓?

Смоделируем наш пример с помощью дерева (так можно представить практически все рекурсивные функции). Каждый вызов – это внутренний узел, а базовые случаи – листья. Дерево для fib(5) выглядит вот так:

Вы можете определить сложность этой функции как O(2n). Каждый вызов по существу приводит к еще двум вызовам – практически идеальный пример экспоненциального удвоения. Другими словами, дерево, представляющее наш код, имеет коэффициент ветвления 2, каждый узел имеет 2 дочерних элемента, поэтому на каждой глубине число узлов удваивается. Из одного узла получается 2, потом 4, потом 8…

Нотация «большое O» – это нечеткая линза, где оценка одновременно рекомендуется и требуется. Но действительно ли эта функция экспоненциально удваивается? Попробуем измерить время выполнения функции fib, определенной выше:

Даже неуклюжий эмпирический анализ намекает на нашу странную петлю. После 32 итераций измерения приобретают знакомую форму…

Компьютеры, часы и интерпретаторы неточны, и постепенно значение time_elapsed становится плохим приближением ряда Фибоначчи:

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

Колония бактерий и ряд Фибоначчи

Можно смоделировать сложность этой функции, используя рекуррентное отношение – формальный математический язык для описания рекурсивных функций. Не пугайтесь этого определения, тут все просто:

Объем работы, который требуется для вычисления n-ного числа, – это объем работы, который требуется для вычисления предыдущих двух цифр вместе взятых. Другими словами, количество листовых узлов в рекурсивном дереве для вычисления n-ного члена последовательности отражает значение этого n-ного члена.

Возьмем конкретный пример:

И f(1), и f(0) в нашем случае постоянны, так как метод просто возвращает 1. Поэтому можно сказать, что:

Если сложить все это снизу вверх, получится следующее:

Вы уже догадываетесь, к чему все это ведет?

Давайте попробуем развернуть формулу для f(5) вместо того, чтобы вставлять в нее реальные значения:

Все эти f(0) и f(1) – это листовые узлы дерева, которые имеют константное значение 1.

Можно ли смоделировать это отношение лучшим способом, чем расширение? Возможно ли создать формулу, которая описывается, сколько f(0) и f(1) будет при разложении конкретного f(n)? Оказывается, возможно! Пристегнитесь, мы входим в зону математического анализа.

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

В каждый момент времени каждая бактерия разделяется на две, поэтому популяция увеличивается вдвое по сравнению с предыдущим моментом. Если начать с одной бактерии, в следующий момент будет уже две, затем 4, 8, 16, 32 и так далее. Это экспоненциальная функция f(n) = 2^n.

Вспомним, что умножение – это просто повторяющееся сложение, и увидим, насколько это похоже на последовательность Фибоначчи:

И тогда:

Есть все основания полагать, что второе выражение также будет расти экспоненциально, но медленнее, чем 2n. С другой стороны, рекурсивное дерево для функции роста бактерий будет иметь больше узлов, чем дерево для fib, хотя в обоих деревьях у узла либо 2 ребенка, либо ни одного. Они похожи, но не идентичны.

Опять золотое сечение

Оказывается, что для «линейных гомогенных рекуррентных отношений с постоянными коэффициентами» можно использовать изящный трюк, для нахождения короткого решения. К счастью, ряд Фибоначчи является таким отношением и мы можем представить его без использования рекурсии (и даже итерации) всего в одной формуле.

Доказательство этого трюка, называемое «теоремой о различных корнях», можно найти здесь.

Мы знаем, что ряд растет по экспоненте, а этот трюк помогает найти «корни» экспоненциальной функции. Он довольно прост: нужно взять нижние индексы функции f и превратить их в экспоненты по переменной r (root – корень), для которой мы их затем решим.

Применим этот трюк для формулы роста бактерий:

На последнем шаге мы делим каждую сторону на r^n-1.

Этот трюк приводит к тому же ответу, что был получен выше – экспоненциальный рост колонии 2n.

Теперь попробуем то же самое для ряда Фибоначчи:

Полученное уравнение можно решить для r, используя квадратичную формулу.

Произошло нечто удивительное, даже если вы этого не заметили. Посчитайте на калькуляторе 1 + sqrt(5) / 2. Вы получите … 1.618: 𝝓, золотое сечение. Поразительно.

Чтобы не потерять лес за деревьями, отметим, что это экспериментально демонстрирует экспоненциальный рост последовательности Фибоначчи с корнем экспоненты 1.618.  Если n-ный член, разделенный на (n-1)-ный член приблизительно равен 𝝓, то умножение (n-1)-ного члена на 𝝓 будет равно n-ному члену.

Отметим также, что второй корень – это другое замечательное число 𝝍 (Psi, пси), которое похоже на золотое сечение и примерно равно -0.618.

Конечно, технически будет правильно сказать, что верхняя граница рекурсивной функции O(2n), все же гораздо более приятно знать, что более жесткая граница – O(𝝓n).

Формула Бине

Следующая часть теоремы о корнях говорит о том, что если наша рекурсия является “линейными однородными рекуррентными отношениями с постоянными коэффициентами”, то мы можем не только установить верхнюю границу ее роста (как сделали только что), но и действительно найти короткое решение.

Вы можете самостоятельно доказать этот замечательный факт.

Это формула Бине, позволяющая определить n-ный член последовательности Фибоначчи:

Это невероятно!

Перевод статьи Fibonacci’s Strange Loop: the beauty of mathematical inception by Tyler Elliot Bettilyon

Больше материалов по алгоритмам:

 

Интересуетесь математикой?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Добавить комментарий