Сложность алгоритма Шенхаге—Штрассена — O(nlog(n)loglog(n))
.
nlog(n)
понятно откуда — мы запускаем БПФ туда и обратно — это O(nlog(n))
, потом перемножаем числа, это O(n)
, потом мы выравниваем коэффициенты — еще O(n)
.
А вот откуда там loglog(n)
берется? Я ошибся с расчетом сложности БПФ? Или что-то еще?
1 ответ
Пусть число в двоичной форме занимает 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))).
O(n\*log(n))
, а приведенная вами сложность - это битовая сложность, она немного отличается от арифметической P.S. это не ответ, а комментарий, т.к. ответа на вопрос я не знаю )n
, то оно содержит порядкаlog n
бит. Представьте себе указатель на этой системе. Чтобы адресоватьX
бит, нужноlog X
бит указателя. ДляX = log n
получаем размер указателяlog log n
. Операции на настолько длинных указателях по идее занимают не константное время, а время, пропорциональное длине указателя.O(n log n)
. Что судя по всему подтверждает моё преположение.