algorithm - Big-Oh : How can O(n) + O(n) + . .. + O(n) 等于 O(n^2)？

Question

我很难理解 Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani - page 24 中的以下陈述它们将 O(n) 的总和表示为 O(n²)。但我对 O(n) 的理解是 n 的线性函数，无论线性函数 added 多少次(对于任何给定的 n)，它都永远不会是二次函数。他们以二进制表示法给出如下 13 x 11 示例的解释。

        1 1 0 1
      x 1 0 1 1
      ----------
        1 1 0 1 (1101 times 1)
      1 1 0 1   (1101 times 1, shifted once)
    0 0 0 0     (1101 times 0, shifted twice)
+ 1 1 0 1       (1101 times 1, shifted thrice)
----------------
1 0 0 0 1 1 1 1 (binary 143)

If x and y (1101 and 1011 here) are both n bits, then there are n intermediate rows, with lengths of up to 2n bits (taking the shifting into account). The total time taken to add up these rows, doing two numbers at a time, is O(n) + O(n) + ... + O(n), which is O(n²), quadratic in the size of the inputs.

抱歉，如果这很明显，但有人可以帮我理解为什么这是 O(n²) 吗？

Answer 1

如果有n个操作复杂度为O(n)，那么总复杂度为n·O(n) 是 O(n²)。