Какой наихудший сценарий для вставки сортировки O (n ^ 2)?

Question

Какой наихудший сценарий для вставки сортировки O(n^2)?

мне кажется, что если сортируемый массив уже отсортирован в обратном порядке, то первый элемент сравнивается 0 раз, второй 1 раз, третий 2 раза и т. Д., И поэтому общее время должно равнятьсяSUM {i=1->i=(n-1)} [n], но это не равно n^2 (например, если n=4, то эта сумма равна 1+2+3=6.

, этот веб-сайт говорит свое, потому что каждая вставка принимает O (n) и есть n из них, так что это O (n ^ 2)., но почему каждая вставка принимает O (n), первая не так, только n-1 вставки могут взять O (n), но и вторая тожеи т. д. только вставки в бесконечность требуют O (n) для вставки (потому что существует бесконечное число элементов с insirtion = O (n) и, таким образом, пробелы, где вставка занимает

Answer 1

Ваш пример верный.

O (n²) означает пропорционально к 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_%7Bn%5Cto%20%5Cinfty%7D%5Cfrac%7Bn%5E2%7D%7B%5Cleft%28%5Cfrac%7Bn%5E2%2Bn%7D%7B2%7D%5Cright%29%7D%20%3D%202.gif

Answer 2

O (n ^ 2) не означает, что операция займет n ^ 2 шага ... Только то, что количество задействованных шагов составляет (приблизительно) n ^ 2 умноженное на некоторое постоянное значение .

В этом случае ваше количество шагов должно напомнить вам о числах гауссова треугольника .Таким образом, это значение для n-1 равно n*(n-1)/2, а для больших чисел n-1 очень близко к n, вы можете аппроксимировать это значение на (n^2)/2 (и, таким образом, константа умножения равна 1/2).