Мы можем выразить сортировку вставкой как рекурсивную процедуру следующим образом. В
порядок сортировки. Чтобы отсортировать A [1..n], мы рекурсивно сортируем A [1..n − 1]
и затем вставьте A [n] в отсортированный массив A [1..n − 1]. Напиши
повторение времени выполнения этой рекурсивной версии вставки
сортировать.
Понятно, что для сортировки массива требуется T (n-1) раз (потому что нам не нужно сортировать последний элемент). Но я не понимаю, почему для вставки элемента в отсортированный массив требуется O (n).
Предположим, у нас есть массив: A = 41;52;26;38;57;9;49. В худшем случае, нам нужно пройти весь массив, чтобы вставить последний элемент n в начало массива. Но я подумал, что это занимает O (n-1) времени, потому что мы проходим n-1 элементов в массиве.
Можете ли вы объяснить мою ошибку и логику правильного ответа?