Анализ алгоритмов сортировки вложений

Question

Я смущен стоимостью и временем алгоритма сортировки вставки в книге «Введение в алгоритмы» 2-го издания от CLRS (стр. 25).

Вот алгоритм с затрат и времени:

Insertion-Sort(A)      cost times 
1. for j <- 2 to length[A]    c1 n 
2.  do key <- A[j]      c2 n-1 
3.  //Insert A[j] into the   0  n-1 
     //sorted sequence A[1..j-1] 
4.  i <- j - 1       c4 n-1 
5.  while i > 0 and A[i] > key   c5 sum_{j=2}^n t_j 
6.   do A[i+1] <- A[i]    c6 sum_{j=2}^n (t_j-1) 
7.   i <- i - 1      c7 sum_{j=2}^n (t_j-1) 
8.  A[i+1] <- key      c8 n-1 

Я не понимаю, почему значение

"times" is equal to n 

для внешнего контура для линии в 1 выше.

Предположим, что у нас есть массив "A", как показано ниже:

A = [5, 2, 4, 6, 1, 3] 

то длина массива 6.

Так,

for j <- 2 to length[A] 

будет означать, мы итерацию от индекс 2 - индекс 6, что в 5 раз.

В этом случае, я думаю, для вышеописанного внешнего цикла мы повторяем (n-1) раз, если n - общее количество элементов в массиве.

Итак, я не уверен, почему значение «раз» только для линии 1 (то есть для цикла out) является n вместо (n-1).

Спасибо.

Энди

Answer 1

Я думаю, что они имеют в виду что-то по следующим направлениям. Петля

for j <- 2 to n 
    do stuff 

эквивалентно следующему:

j <- 2 
while j <= n 
    do stuff 
    j <- j+1 

который будет проверять его состояние для j равно 2, 3, ..., n, иn+1. Таким образом, необходимо выполнить сравнения n, хотя тело цикла выполняет только n раз.

Может быть полезно рассмотреть крайний случай: предположим, что n = 2. Тогда мы будем: установить j = 2, проверить j < = n (да), сделать материал, установить j = 3, проверить j < = n (нет), сделано. Два сравнения j против n, а не только один.

Answer 2

Спасибо за все ответы. На мой взгляд, неутешительно, что авторы явно не обсудили свое намерение о том, как они определили функцию стоимости для каждой из строк в этом Псевдокоде. Очень плохой способ произвести впечатление на ученика или студентов, или на работающих профессионалов (таких как я), которые собирают анализ алгоритмов через два десятилетия пробела!

Еще раз спасибо. Вы все просто потрясающие, каждый раз мне нужна была помощь.