What is the time complexity of adding n numbers

问题:

If I have to add arbitrary numbers like the numbers 1,12,14,71,83,21... then what would be the time complexity of this operation?

I know that adding two numbers is O(1), but how about a list of n numbers. Assuming I'm using the best possible data structure to store them for this purpose, if at all that can have any impact on the process!

Thanks in advance!

回答1:

Adding 2 numbers is O(1) since the operation itself is constant time and the input is fixed. Regardless of the input, the operation will always take the save time.

Moving to a collection of items, the operation is still constant time, but now it's being done multiple times. The larger the input size (N), the longer it will take, and the growth rate will be linear - for each extra item in the input, the operation will take 1 more cycle.

Because of that, the time complexity is O(N).

回答2:

It's O(N). Each data-point must be hit at least once.

However, assuming your question is practical rather than theoretical: If you have N/2 cores capable of adding two numbers in a single cycle, you can perform the operation in log2(N) cycles. Pseudocode for a fast parallel approach:

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

as opposed to a naive approach:

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

The bottleneck preventing parallelization in the naive case is the 'reduction' into accum. I think any commutative reduction operation (addition, scalar multiplication, etc) can be parallelized as above.

Another practical consideration is that CPU and GPU processor cores that can do more than one addition in a single "cycle" (eg SSE).

Big-O doesn't highlight reduction bottlenecks and does not necessarily reflect time complexity measured in real time.

回答3:

It would be O(N). For example in pseudo-code, whereas list contains the numbers:

while(list[i] != end) { //n in the size of the list, so O(N)
    sum += list[i]; //O(1)
    i++;  //O(1)
}

No matter what the structure is, it would always be O(N), since you must check (add) each and every element.