1 
                                //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

私が理解していないのは、なぜ最初の1つの時間がn-1ではなくnであるのかということです。また、総和では、なぜそれがwhileループのt（j）対t（j）-1からのものであるのか。それらは定数なので、それは本当に問題ではないことを私は知っていますが、それでも私には混乱しています。ありがとう！これはCLRSアルゴリズムの教科書からのものです。挿入ソート。

4

1 に答える 1

1

次のようなforループの場合：

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

条件j < 4は、j = 2、j = 3、およびj=4の場合の3回テストする必要があります。ループ本体は、j=2とj=3の2回だけ実行されます。最後の「false」条件は、追加のテストとしてカウントされます。

于 2012-08-24T18:41:41.740 に答える