每列快速求和。可能？

enter image description here

是否有可能找到每列和所有列比为O更快（N^2）？首先，我认为有可能使它成为n * log（n），如果我们像这样重新组合总和（在时间上总共2行，然后剩余2行，然后剩下2行...）：

enter image description here

但是，然后我计算了加号的数量，结果在两种情况下都是相等的 - 7 = 7。所以有可能在n * log（n）时间内组合这样一个总和，或者我自己愚弄了（我知道有FHT或FFT类似于变换，所以可能是这种情况）？

2012-03-28 Vadim

什么是n？我的意思是对于我来说，n = 8和m = 10，你有'（n-1）* m'加号 – hroptatyr 2012-03-28 10:40:51

@ hroptatyr：由于我画了不同的n和m，我用了n^2和n * log （n）只是为了简单。但是，我们可以假设n = m = 8例如 - 没有太大的区别。 – Vadim 2012-03-28 11:19:29

@hroptatyr：n是行数。 m - 列数。 – Vadim 2012-03-28 11:20:01

不，我们的输入大小是O(n^2)，所以我们的算法不能比这个速度快（因为我们使用的是所有的输入值）。

这是假定n是行数，矩阵是正方形（给出n^2），并且元素之间没有特殊关系。

2012-03-28 10:39:29 orlp

@amit：如果我们知道每个数组都表示采样的正弦曲线，它是否会改变某些内容？（但是它们的总和不是周期性的波形，所以我们不能使用FFT） – Vadim 2012-03-28 11:36:08

@Vadim：除此之外，每个值都在0-1的范围内，几乎没有什么。 – orlp 2012-03-28 12:37:27

不需要。您需要从内存中读取（至少）n^2个项目，这需要（至少）O（n^2）时间。

_{1.假设n是列数（或行数）。}

2012-03-28 10:38:59

除非你对矩阵有更多的了解，否则不可能做得更好，然后O(n^2)。

您需要阅读矩阵中的每个元素，以获得正确的总和为每列，所以你得到一个下界Omega(n^2)

另外请注意，你的想法是O(n^2)，因为即使在第一次迭代，你总结有n * (n/2) sum ops，它是O(n^2)

2012-03-28 10:39:11 amit

回答