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）vs 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 时。最后的“假”条件算作额外测试。