Я пытаюсь вычислить T(n) для этой функции, и то, что я придумал, это T(n) = T(n) + T(n) + O(1). У меня есть буксир T (n) для 2 рекурсивных вызовов функции g (), а затем O (1) для всех операций с постоянным временем, таких как сложение. Я чувствую, что я далеко, поэтому любая помощь будет принята с благодарностью, мой математический фон не слишком хорош.
int g(int y) {
if (y <= 0) {
return 1;
}
else {
return g(y - 1) + g(y - 2);
}
}
временная сложность вычислений числа Фибоначчи зависит от используемого алгоритма. Существует как минимум 4 алгоритма их вычисления (с разной временной сложностью):
Сначала отметим, что мы можем понять это, посмотрев на граф вызовов рекурсивной функции Фибоначчи. .
Callgraph на самом деле является деревом.
Мы можем свести все к тому, чтобы узнать, сколько узлов у этого дерева.
Количество узлов в графе вызовов для F(n) имеет корень и количество узлов в графе вызовов F(n-1) + количество узлов в графе вызовов F(n-2).
Мы будем обозначать количество узлов в F(n) через L(n) (и вы увидите, что буква L не случайна).
Как мы описали выше, L(n) = L(n-1) + L(n-2) + 1.
Но подождите, есть еще! Оказывается, это точно числа Леонардо, и они имеют общая закрытая форма:
( "a(n) is the number of nodes in the Fibonacci tree of order n." A001595)
Существует еще один алгоритм, включающий запоминание, который имеет сложность O(n) (вот пример и еще один). Это включает в себя сохранение результатов T(n) в векторе и постепенное вычисление T(n) для n=1 до требуемого n.
Если вы хотите быть действительно очень правильным, это также не O (n), поскольку предполагается, что числовая стоимость добавления равна O (1), однако ... по мере того, как F (n) становится больше, стоимость добавления два числа Фибоначчи равны O(n). Вы можете узнать больше об этом здесь. , это прекрасное изложение этого. Таким образом, фактическая сложность этой реализации составляет O(n^2).
Существует также другой алгоритм сложности O(1), если вы используете арифметику произвольной точности или умное округление. Это происходит из формулы Бине. Доказательство формулы Бине см. в разделе 1.3 на стр. 13 здесь с помощью генерирующих функций или вы можете найти собственное разложение матрицы, а затем использовать его для вычислить энную степень . После этого ваша формула в закрытой форме окажется в одной из ячеек n-й матрицы мощности.
Если вы хотите быть очень точным, на самом деле это O(log(n)), так как это возведение в степень путем возведения в квадрат (также называемый повторным возведением в квадрат, алгоритмом двоичного усиления или двоичным возведением в степень), который вы используете вычислить формулу Бине.
Обычно мы предполагаем, что степень x^n равна O (1), но это не так, это O (log (n)) в количестве умножений. Чтобы быть по-настоящему точным, вы должны учитывать стоимость умножения, которая зависит от алгоритма умножения используется.
Вот формула Бине, кстати:
Вот как выглядит последовательность Фибоначчи в матричной форме:
Вот возведение в степень в квадрате:
ОБНОВЛЕНИЕ 2015-06-29:
Есть еще один подход к вычислению чисел Фибоначчи в O(log(n)) . Используются два идентификатора
Они позволяют вычислять F(2*n+1) на основе F(n),F(n+1) и F(2*n) на основе F(n-1),F(n),F(n+1). Алгоритм находит старший значащий бит n и повторяется до наименее значащий бит при использовании идентификаторов по пути для вычисления числа Фибоначчи. Здесь есть реализация алгоритма. Два идентификатора могут быть получены (как в предыдущей ссылке) в квадратичном поле ℚ( √5) или они могут быть получены из n-й и 2n-й степеней матрицы, упомянутой выше (см. раздел 2.5, озаглавленный «Матричные методы», на стр. 23 документа «Алгоритмы быстрого вычисления чисел Фибоначчи» Дж. Л. Холлоуэя) .
Рекуррентное соотношение выглядит следующим образом:
T(n) = T(n-1) + T(n-2) + O(1)
Это не будет соответствовать ни одному из случаев в соответствии с Основной теоремой, потому что в вашем уравнении нет члена в форме T (n/b).
Таким образом, мы должны использовать несколько странный подход:
Поскольку T(n-1) по приведенному выше определению будет равно T(n-3) + T(n-2) + O(1), вы можете записать T(n) как:
T(n) = 2T(n-2) + T(n-3) + 2*O(1)
Поскольку T(n-2) = T(n-3) + T(n-4) + O(1), мы можем дополнительно упростить T(n) следующим образом:
T(n) = 3T(n-3) + 2T(n-4) + 3*O(1)
К настоящему времени мы должны начать видеть закономерность, но давайте просто сделаем еще один шаг вперед для верной меры. Поскольку T(n-3) = T(n-4) + T(n-5) + O(1):
T(n) = 5T(n-4) + 3T(n-5) + 4*O(1)
Коэффициент первого члена соответствует образцу последовательности Фибоначчи. В следующем раунде у нас будет 8T(n-5) в качестве ведущего члена. Второй член также следует последовательности Фибоначчи, так как в следующем раунде у нас будет 5T (n-6). Третий член просто растет, как и n.
Итак, поскольку T (1) - это просто O (1), вы получите:
T(n) = x*O(1) + y*O(1) + n*O(1), где x — n-й член в последовательности Фибоначчи, а y — (n-1)-й член в последовательности Фибоначчи. .
Глядя на начальный термин, вы можете видеть, что наш анализ большого O в основном представляет собой формулу для вычисления x на основе n.
Эту формулу можно увидеть здесь: http://www.askamathematician.com/2011/04/q-is-there-a-formula-to-find-the-nth-term-in-the-fibonacci-sequence/
Когда вы примените свой анализ большого O, все это сведется к следующему: O (1,6 ^ n)
Fib(0) = 0иFib(1) = 1. В данном случаеg(-1) = 1иg(0) = 1. - person Gio Borje schedule 22.03.2013