performance - n个数相加的时间复杂度是多少

Question

如果我必须添加任意数字，例如数字 1,12,14,71,83,21... 那么此操作的时间复杂度是多少？

我知道将两个数字相加的复杂度为 O(1)，但如果是 n 个数字的列表呢？假设我为此目的使用尽可能最好的数据结构来存储它们，如果对过程有任何影响的话!

提前致谢!

Answer 1

它是O(N)。每个数据点必须至少命中一次。

但是，假设您的问题是实际问题而不是理论问题:如果您有 N/2 核心能够在单个周期内添加两个数字，您可以在 log2(N ) 循环。快速并行方法的伪代码:

while N > 1:
    N = N / 2
    for i in 0..N: // in parallel
        X[i] += X[i + N]
// result in X[0]

与天真的方法相反:

 accum = 0
 for i in 0..N: // in serial
     accum += X[i]
 // result in accum

在原始情况下阻止并行化的瓶颈是“减少”到accum。我认为任何可交换归约运算(加法、标量乘法等)都可以像上面那样并行化。

另一个实际考虑是 CPU 和 GPU 处理器内核可以在单个“周期”中执行多个加法(例如 SSE)。

Big-O 不会突出缩减瓶颈，也不一定反射(reflect)以实时衡量的时间复杂度。