哦：O（n）+ O（n）+ ... + O（n）如何等于O（n ^ 2）？
我很难理解S. Dasgupta，CH Papadimitriou和UV Vazirani的算法中的以下陈述，他们将O（n）的总和表示为O（n2）。 但是我对O（n）的理解是n的线性函数，无论线性函数添加了多少次（对于任何给定的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)
如果x和y（这里的1101和1011）都是n位，那么有n个中间行，长度最多为2n位（考虑到移位）。 将这些行相加所需的总时间，一次执行两个数字，即O（n）+ O（n）+ ... + O（n），即O（n2） ，其大小为二次方投入。
对不起，如果这是显而易见的，但有人可以帮我理解为什么这是O（n2）？
如果你做了一些需要N秒的事情，并重复N次。 需要几秒钟才能完成？
N = 2 => 2*2 seconds.
N = 3 => 3*3 seconds.
N = 4 => 4*4 seconds.
=> N^2 seconds.
如果有n个操作的复杂度为O（n），那么总的复杂度为n·O（n），即O（n2）。
如果它乘以一个常数因子，那么O（n）不是O（n2）**。
n is O(n)
7n is O(n)
100000n is O(n)
n*n is O(n^2)
以下是维基百科引用的big-O的正式定义：
令f（x）和g（x）是在实数的一些子集上定义的两个函数。 一个人写道
当且仅当对于足够大的x值，f（x）至多是绝对值乘以g（x）的常数。 即，当且仅当存在正实数M和实数x0时，f（x）= O（g（x）），
**警告：大O是一个上限。 所有的O（n）在技术上也是O（n2）。 请参阅Big Theta和Big Omega的区别。
http://en.wikipedia.org/wiki/Big_O_notation
链接地址: http://www.djcxy.com/p/6807.html上一篇: Oh : How can O(n) + O(n) + ... + O(n) be equal to O(n^2)?