插入排序O(n ^ 2)的最坏情况是什么？

Question

插入排序的最坏情况是什么O(n^2)？

我觉得如果要排序的数组已经按相反的顺序排序,那么第一个元素将比较第二个1次,第三个是2次,依此类推,所以总时间应该等于SUM {i=1->i=(n-1)} [n]但不等于n^2(例如,如果n=4那么总和是1+2+3=6.

这个网站说它因为每次插入都需要O(n)和那些那些O(n ^ 2).但是为什么每次插入都需要O(n),第一次插入不需要n-1插入可以取O(n)但第二次插入也不需要等等.只有插入无穷大的插入才能插入O(n).(这是因为有无数个元素,带有insirtion = O(n),所以插入需要的oens

Answer 1

你的例子是对的.

O(N²)指比例为N² Ñ接近无穷大,不一定相等N²对于所有的n.

更确切地说,为了表明f(n)和g(n)在n增长到无穷大时是成比例的,你需要表明

\ lim_ {n\to\infty}\frac {f(n)} {g(n)} = c http://www.texify.com/img/%5CLarge%5C%21%5Clim_%7Bn%5Cto% 20%5Cinfty%7D%5Cfrac%7BF%28N%29%7D%7BG%28N%29%7D%20%3D%20c.gif

对于一些有限的非零常数c.在这种情况下,你会得到类似的东西

\ lim_ {n\to\infty}\frac {n ^ 2} {\ left(\ frac {n ^ 2 + n} {2}\right)} = 2 http://www.texify.com/img/ %5CLarge%5C%21%5Clim_%70亿%5Cto%20%5Cinfty%7D%5Cfrac%70亿%5E2%7D%7B%5Cleft%28%5Cfrac%70亿%5E2%20亿%7D%7B2%7D%5Cright%29 %7D%20%3D%202.gif