algorithm - 关于从clrs书中计算算法的复杂性

Question

                                //Number of times 
for j=2 to A.length`          //n
    key = A[j]      //n-1
    i=j-1         //n-1
    while i>0 and A[i]>key    //summation of j from 2 to n of t(j) 
       A[i+1]= A[i]        //summation from j from 2 to n of t(j)-1
       i=i-1               //ditto
    A[i+1]=key   //n-1

我不明白的是为什么第一个for one的次数是n而不是n-1？并且在总结中为什么它来自 while 循环中的 t(j) 与 t(j)-1。我知道这真的无关紧要，因为它们是常量，但它仍然让我感到困惑。谢谢!这是CLRS算法课本上的插入排序。

Answer 1

对于 for 循环，例如:

for(int j = 2; j < 4; j++) {}

条件j < 4需要测试3次:j=2、j=3、j=4时。循环体只会运行 2 次:当 j=2 和 j=3 时。最后的“假”条件算作额外测试。