|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 27 Jul 2001 01:46:54
To : All
Subject : Re: Числа фибоначи
--------------------------------------------------------------------------------
"Max Alekseyev" <Max.Alekseyev@f60.n5015.z2.fidonet.org> wrote in message
news:996188323@f60.n5015.z2.ftn...
> SK> Побаловался немного с числами Фибоначи и сделал алгоритмик
> SK> сложности ln(N) для поиска N-го числа Фибоначи.
> SK> Известен ли подобный алгоритм в литературе?
> SK> Hе очень сложно, но в инете никаких ссылок на подобное не нашел.
> Это ничего не значит.
Это правда.
> n
> / F(n) F(n-1) \ / 1 1 \
> ( ) = ( )
> \ F(n-1) F(n-2) / \ 1 0 /
>
> Используешь дихотомичное возведение в степень и получаешь как раз
сложность
> порядка ln(n).
Да, действительно просто.
Т.е разбиваем номер на сумму степеней двойки,
n =2^k+2^m+...
строим матрицы до максимального разряда k<log_2(n).
И затем произведение матриц для ненулевых компонентов.
Hо это уже ln(ln(n))
> SK> Обычно считают в лоб.
>
> Кто тебе такую глупость сказал?
Hикто, это относилось к моим недлительным и бесплодным
поискам в интернете. По видимому часто эта задачка используется
как упражнение для программирования, и я только на такие вещи
и натыкался. Если 99% случаев можно считать за обычно,
то тогда "обычно считают в лоб" ;). Just kidding.
Thanks,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
