求和长n

Question

我知道这是一个简单的问题，但是我被与线性代数问题相关的一些补充让我感到不安，被视为恒定时间与线性时间。在这种情况下，我有兴趣将长度n elementwise的m向量求和。我认为复杂性是O（N）或O（MN）。我很困惑，因为如果我们一次去两个，但只有n个单独的添加问题，总共需要（M-1）n添加。看到它的正确方法是什么？是否从算法或硬件实现的角度看，这是否重要？

Answer 1

否，某些算法的Big-O复杂性始终取决于一个人如何构成问题。您基本上选择了您关心的变量。例如，我们可以想象一些应用程序总是添加有10个元素的向量。在这种情况下，上面的n是常数10，因此从分析该应用程序的行为的角度来看，Big-O仅是O（m）。 与“硬件实现”的观点有关，如果您的意思是使用什么硬件来实现某些算法，而不是是的，如果我们考虑到它，它可能会影响时间复杂性。在理想情况下，矢量化的SIMD/GPU执行可以使其更接近O（M）。平行还原可以减少到O（n log M）。理论上的复杂性仍然是O（MN），但实际的性能取决于并行性，是的。