|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/400 25 Apr 2002 15:18:12
To : Borodin Anatoly
Subject : Re: Фибоначчи
--------------------------------------------------------------------------------
Tue Apr 23 2002 20:41, Borodin Anatoly wrote to Vovanius Uryvaeff:
BA> From: Borodin Anatoly <fractal@viii.ntu-kpi.kiev.ua>
BA> Hi!
>> a2 = a*a1+b*b1
>> b2 = a*b1+b*c1
>> c2 = b*b1+c*c1
>> он считает наиболее быстро. как то что то здесь уже пролетало
BA> IMHO, умножение, даже целых чисел, не самая быстрая операция по
BA> сравнению со сложением-вычитанием
BA> Чем обеспечена скорость приведённого тобой алгоритма (если чем-то
BA> обеспечена)???
ну.. он вычисляет значение за log2(N) проходов цикла...
хотя, может ты прав, если размер чисел возрастает пропорционально номеру члена
то время нужное для моей программы = O(log2(N)*N^2) (log2(N)циклов при времени
умножения = O(N^2), а простого = O(N^2) (N циклов сложения при времени
сложения O(N)... может я неверно оценил время...
впрочем так вычислять остаток от деления числа фибоначчи наверное быстрее.
...сижу тут, никого не трогаю, примус починяю...
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
