Итак, я вычисляю числа Фибоначчи по формуле Бине с библиотекой GNU MP. Я пытаюсь определить асимптотическое время выполнения алгоритма.
Для Fib (n) я устанавливаю переменные равными n битам точности; таким образом, я считаю, умножение двух чисел это n Log (n). Возведение в степень, я полагаю, n Log (n) умножений; поэтому я считаю, что у меня есть n Log (n) Log (n Log (n)). Верно ли это как в предположениях (умножение чисел с плавающей запятой, так и на умножение в возведении в степень с целым показателем степени) и в заключении?
Если моя точность высока, и я использую точность g (n); тогда я думаю, что это сводится к g (n) Log (g (n)); однако я думаю, что g (n) должно быть g (n) = n Log (phi) +1; что не должно иметь реального влияния на асимптотику.