Учет временной сложности вставки массива

Question

Учитывая сортировку вставки в массиве, где вы выполняете O (n) сравнений, чтобы найти индекс для вставки, а затем вставки, будет ли сложность времени O (n ^ 3)?

Так как для каждого элемент (n), вы перебираете отсортированный список (n), затем вставляете (n).

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

Psuedocode для вставки O (n ^ 3):

for element in array
    find the correct location
    then insert in the correct location

Answer 1

Вы очень близки к тому, чтобы получить правильный ответ, но правильное время ограничено здесь O (n ² ).

Вы правы, что вам нужно посетить каждый элемент массива, так что вы будете делать что-то O (N) раз. И что это такое? Как вы заметили, вы сначала находите точку вставки (которая занимает время O (n)), а затем вы перемещаете вещи вниз, чтобы освободить место (что также требует времени O (n)). Это означает, что проделанная работа за элемент является O (n) + O (n) = O (n). В своем анализе вы умножили эти два O (n) слагаемых вместе, поэтому вы переоцениваете общее количество.

В целом вы выполняете O (n) работу O (n) раз, так что хорошо верхняя граница всей выполненной работы - O (n ² ).

Answer 2

Вы очень близки к тому, чтобы получить правильный ответ, но правильное время ограничено здесь O (n2).