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