我是多线程算法的新手，我正在尝试重新编码累积和函数以获得比 O(n) 更好的复杂度。 你有什么提示吗？或者我们不能比 O(n) 更好？
我尝试使用分而治之的方法，但没有得到执行的结果。尝试了一些并行循环，但也没有得出结论。
感谢您的帮助
嗯，非常近似地说，如果您有 k 核心和一个非常可并行化的问题（这就是），那么您应该能够将您所花费的时间除以 k 与并行性。
问题是，k是固定的，而n不是。当 k 为常数时，O(n/k) 与 O(n) 相同。它会走得更快，但不会渐近更快。
在抽象原理中，您的分而治之算法可能会在 O(log(n)) 时间内运行，但需要 O(n) 处理器才能做到这一点。
因为 k 是固定的，多线程算法永远不会改善其渐近时间，只会改善常数因子。您的并行实现的完成时间可能是单线程实现的十分之一或二十分之一，但不是时间的对数或时间的平方根。