3

Сложность алгоритма Шенхаге—Штрассена — O(nlog(n)loglog(n)).
nlog(n) понятно откуда — мы запускаем БПФ туда и обратно — это O(nlog(n)), потом перемножаем числа, это O(n), потом мы выравниваем коэффициенты — еще O(n).
А вот откуда там loglog(n) берется? Я ошибся с расчетом сложности БПФ? Или что-то еще?

4
  • 1
    Арифметическая сложность этого алгоритма O(n\*log(n)), а приведенная вами сложность - это битовая сложность, она немного отличается от арифметической P.S. это не ответ, а комментарий, т.к. ответа на вопрос я не знаю )
    – BOPOH
    24 фев 2015 в 5:35
  • Возможно, тут учитывается расход на реально огромные числа. Если ваше число имеет порядок n, то оно содержит порядка log n бит. Представьте себе указатель на этой системе. Чтобы адресовать X бит, нужно log X бит указателя. Для X = log n получаем размер указателя log log n. Операции на настолько длинных указателях по идее занимают не константное время, а время, пропорциональное длине указателя.
    – VladD
    24 фев 2015 в 13:08
  • Из TAOCP/4.3.3: > If we allow ourselves a more powerful computer, with random access to any number of words of bounded size, Schönhage has pointed out that the upper bound drops to O(n log n). Что судя по всему подтверждает моё преположение.
    – VladD
    24 фев 2015 в 13:13
  • Похоже, вы правы. Переведите комментарий в ответ, пожалуйста!
    – Zelta
    27 фев 2015 в 20:05

1 ответ 1

4

Пусть число в двоичной форме занимает nбит - это многочлен, представляемый битовым массивом коэффициентов. Перемножение двух чисел эквивалентно линейной свёртке этих массивов.
Быстрый алгоритм циклической свёртки двух массивов имеет вид:

a(*)b = FFT-1(FFT(a)FFT(b)).

Он превращается в алгоритм линейной свёртки при дополнении массивов нулевыми коэффициентами до степени результата (если разрядности чисел одинаковы, это удвоенная разрядность).

FFT имеет сложность O(nlogn) операций. При этом на каждый новый элемент приходится O(logn) операций сложения с весами, что повышает разрядность c 1 бита до O(log log n).
FFT-1 имеет сложность того же порядка.
Переносы битов через разряды - это n сложений разрядности O(log log n).
Перемножение спектров - это n умножений разрядности O(log log n), сложность каждого умножения не выше O(log2 log n).

Битовая сложность по операциям:

2 прямых FFT: O(n log(n) log(log(n)))

Перемножение спектров: O(n log2(log(n)))

FFT-1: O(n log(n) log(log(n))).

Переносы битов через разряды: O(O(n log(n) log(log(n))))

Итого: O(n log(n) log(log(n))).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.