Разъяснение по БПФ

Question

Я знаю, что в следующих рассуждениях что-то не так, но я не уверен, что именно.

БПФ:

1. даны два многочлена

   A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

   и

   B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

   вы можете вычислить коэффициенты произведения

   AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

   в O(n log n ) время.

2. Итак, даны два вектора (a_0, ..., a_n) и (b_0, ..., b_n) мы можем вычислить вектор v_i = \sum j = 0 ^ k ( a_j b_{k-j}) в O(n log n) время (путем встраивания векторов в нули.)

3. Учитывая вышесказанное, мы должны быть в состоянии вычислить точечное произведение A =(a_0, ..., a_n) и B =(b_0, ..., b_n) который является A.B = \sum_j=0 ^ n a_j b_j в O(n log n) время путем предварительной обработки одного из векторов, скажем B быть B' = (b_n, b_{n-1}, ..., b_1, b_0) затем вычисляем свертку, как в 2.в O(n log n) время.

Если приведенные выше рассуждения верны, то это означает, что мы можем реализовать Матричное умножение двух nxn матрицы в O(n^2 log n ) время путем вычисления скалярного произведения в O(n log n) время O(n) времена.

Однако наилучшее время выполнения для умножения матриц, которое мы знаем, составляет около O(n^2.4) таким образом, это кажется маловероятным, что, вероятно, означает, что один из шагов 1,2 или 3 неверен.

Answer 1

Есть такие n^2 записи в продукте, а не n и таким образом, этот алгоритм был бы O(n^2 * n * log n) = O(n^3 log n).

И лучшим алгоритмом для вычисления точечных произведений является O(n), не O(n log n).Вот почему наивным алгоритмом умножения матриц является O(n^3).(Это n^2 точечные продукты, которые могут быть выполнены в O(n) время).

Answer 2

Интересно, почему достижением является то, что на шаге 3 вы можете вычислить точечное произведение за O (n log n) время, поскольку хорошо известно, что точечное произведение может быть вычислено за O (n) время?Также шаг 2 выглядит как линейное время вместо шага O (n log n)?

Также вывод об O (n ^ 2 log n) не следует логически.Вы не можете взять скалярное произведение O (n) раз, приводящее к матрице AB - насколько я знаю, вы должны взять O (n ^ 2) скалярных произведения, что приводит (согласно вашему анализу) к O (n ^ 3 log n), что уступает стандартному O (n ^ 3).Это из-за вашего странного результата точечного произведения O (n log n).