Время работы Insertion-Sort

Question

В моей книге они рассчитали время выполнения сортировки ввода на входе n.Алгоритм:

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

И моя проблема в том, почему времена = n в строке 1?Почему не просто n-1 раз?

Answer 1

Что ж, с моей точки зрения, дополнительные затраты времени 1 не в инициализации на самом деле, потому что после n-1 успешное управление итерациями вернется к условию i <= (length (A)) и сравнит i с длиной A.Эта 1 дополнительная стоимость сравнения добавлена ​​в цикл. </p>

Это объясняется на странице №.25 Введение в алгоритм по Cormen.

Answer 2

На странице 25 CLRS «Когда цикл for или while выходит обычным способом (т. Е. Из-за теста в заголовке цикла), тест выполняется в один раз больше, чем тело цикла»Это означает, что условие выхода будет выполнено еще раз перед выходом из цикла for или while.

Answer 3

Думайте об этом с точки зрения цикла for в C:

for (int i = 2; i <= length(A); ++i) ...

Эта строка достигается n раз - один раз для инициализации и n - 1 раз для приращения и проверки.