|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 23 Apr 2003 11:58:48
To : Evgeniy Jirnov
Subject : Re: Дискретное преобазование Фурье.
--------------------------------------------------------------------------------
"Evgeniy Jirnov" <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org> wrote in
message news:1051055281@p13.f1230.n5030.z2.ftn...
> Мир твоему дому, All.
>
> Подскажите где можно что-нибудь прочитать по поводу сабж?
> Интересует именно теория, конкретно пункт "Зачем нужно?".
> Формулы я знаю. Меня интересует зачем так преобразовывать график...
С какой сложностью работает оптимальный алгоритм, перемножающий 2 очень
больших числа (скажем по 2048 битов)? Алгоритм умножения "в столбик" даёт
оценку O(N^2), в то время как с помощью преобразования Фурье получаем
O(NlogN) и этот алгоритм является ассимптотически лучшим среди существующих
(и даже теоретически оптимальным).
Желаю удачи,
Дмитрий Ясенев
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
