用特殊的归约式|（i*2）总结一个数组

Question

我目前正在处理一个在网上发现的java问题。

我们假设我们有一个数组，它有几千个，如果不是数百万个条目的话。目标是高效快速地得到数组的全部和。

第一种方法是简单地总结它。这是我解决它的方法：

for (int i = 0; i < array_size; i++) sum += array[i];

另一条路是艰难的。在在线任务中，描述了使用某种还原。你应该把所有相邻的元素加起来，然后每秒钟加一次，然后每四分之一，每八分之一。。。在最后到达[0][max]之前，[0]是数组的总和。

如果有人能帮助我或引导我走向正确的方向，我将非常感激。

Answer 1

您的实现已经是O（n）-您无法再做得更好了。你需要O（1）-空间，所以这也不能减少。

您只能尝试改进运行时（而不是复杂性），例如通过使其对缓存更友好或将其隔离，希望这可以提高速度（但对于像添加这样简单的任务，我认为内存访问是一个瓶颈）。