插入排序的运行时间

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

我的问题是为什么第一行中的times=n？为什么不是n-1次？

Answer 1

考虑一下C中的for循环：

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

这条线到达n次-一次用于初始化，n-1次用于增量和测试。

Answer 2

在我看来，额外的1次时间成本实际上不是初始化，这是因为在n-1次成功迭代后，控制将返回到i<=(长度( A ))条件，并将i与长度A进行比较。这1次额外的比较成本被添加到循环中。

这件事在科尔曼算法导论的第25页上有解释。

Answer 3

在CLRS的第25页上，“当for或while循环以通常的方式退出时(即，由于循环头中的测试)，测试将比循环体多执行一次。”这意味着在退出for或while循环之前，将再次执行退出条件。