请看这张图:
是否有可能比 O(n^2) 更快地找到所有列的每列总和？
首先，我认为如果我们像这样重新组合求和(一次求和 2 行，然后剩余 2 行，然后剩余 2 行......)，则有可能使其成为 n * log(n):
但后来我计算了加号的数量，结果在两种情况下都是相等的 - 两张图片都是 7 = 7。
那么是否有可能在 n * log(n) 时间内得出这样的总和，或者我自欺欺人(我知道有 FHT 或 FFT 之类的变换，所以可能是这种情况)？
最佳答案
不，我们的输入大小是 O(n^2)，所以我们的算法不能比这更快(因为我们正在使用所有输入值)。
这是假设 n 是行数，矩阵是正方形的(给定 n^2)并且元素之间没有特殊关系。
关于c++ - 快速的每列求和。可能的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9905729/