Быстрое суммирование по столбцам. Возможный?

Question

Пожалуйста, посмотрите на эту картинку:

Можно ли найти сумму по столбцам для всех столбцов быстрее, чем в O (n ^ 2)?

Сначала я подумал, что можно сделать это n * log (n), если мы перегруппируем суммирование следующим образом (чтобы сложить 2 строки за раз, затем оставшиеся 2 строки и затем оставшиеся 2 строки ...):

Но затем я посчитал количество плюсов, и оно оказалось одинаковым в обоих случаях - 7 = 7 на обоих рисунках.

Так можно ли составить такоесумма за n * log (n) времени, или я сам себя одурачил (я знаю, что есть FHT или FFT-подобные преобразования, так что может быть и так)?

Answer 1

Это не может быть сделано лучше, чем O(n^2), если у вас больше знаний о матрице.

Вам нужно прочитать каждый элемент в матрице, чтобы получить правильную сумму для каждого столбца, чтобы вы получили нижнюю границу Omega(n^2)

Кроме того, обратите внимание, что ваша идея O(n^2), потому что даже на первой итерации вы суммируете n * (n/2) sum ops, что составляет O(n^2)

Answer 2

Нет, наш входной размер равен O(n^2), поэтому наш алгоритм не может быть быстрее этого (потому что мы используем все входные значения).

Предполагается, что n - это количество строк, матрица квадратная (что дает n^2), и между элементами нет особого отношения.

Answer 3

Нет.Вам нужно прочитать (как минимум) n ^ 2 элементов из памяти, что занимает (как минимум) O (n ^ 2) время. ¹

---

_{1.Предполагая, что n - это число столбцов (или количество строк).}