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 

而我的问题是为什么在第1行的时间= n？为什么它不仅仅是n-1次？

Answer 1

想想它的条款环路C：

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

到达此行ñ次 - 一次初始化，并ñ - 1次增量 - 和 - 测试。

Answer 2

那么在我看来，额外的1时间成本并不是初始化，事实上这是因为在n-1成功的迭代控制将返回到i < =（长度（A））条件并将i与长度A 。这1个额外的比较成本加入到循环中。

这件事在页码解释。 Cormen算法介绍25。