Oh : How can O(n) + O(n) + ... + O(n) be equal to O(n^2)?
I'm having a hard time understanding the following statements from Algorithms by S. Dasgupta, CH Papadimitriou, and UV Vazirani - page 24 that they represent the sum of O(n) as O(n2). But my understanding of O(n) is a linear function of n, and it can never be quadratic no matter how many times the linear functions are added (for any given n). They are giving the explanation like below for the example of 13 x 11 in binary notation.
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(n2) , quadratic in the size of the inputs.
Sorry if this is obvious, but could somebody please help me understand why this is O(n2)?
If you do something which will take N seconds, and repeat that N times. How many seconds will it take to finish?
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）。
Something that is O(n) isn't O(n2)** if it's multiplied by a constant factor.
n is O(n)
7n is O(n)
100000n is O(n)
n*n is O(n^2)
Here's the formal definition of big-O, quoted from Wikipedia:
Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes
if and only if, for sufficiently large values of x, f(x) is at most a constant multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that
** WARNING: Big O is an upper boundary. Everything that's O(n) is also technically O(n2). See Big Theta and Big Omega for distinction.
http://en.wikipedia.org/wiki/Big_O_notation
链接地址: http://www.djcxy.com/p/6808.html上一篇: O时间复杂度