口算法运行肘间与输入规模和输入分布有关,如插入排序: INSERTION-SORT(A) times for(i=2; i<=length A: ++ 2 key=AlI -1 ∥ nsert All into the sorted sequence All1…j10 -1 i=i-I while(i>0&&Ali> key Ai+1=Ai Ali+1=key -1 7(m)=cn+c(n-1)+c(m-1)+c∑1+c∑(1-1)+c∑(1-1)+c(n-1) 2021/2/82021/2/8 3  算法运行时间与输入规模和输入分布有关，如插入排序： 1 2 4 5 6 7 8 2 2 2 ( ) ( 1) ( 1) ( 1) ( 1) ( 1) n n n j j j j j j T n c n c n c n c t c t c t c n = = = = + − + − + + − + − + −    INSERTION-SORT(A) cost times 1 for( j = 2; j <=length[A]; j++) c1 n 2 { key = A[j] c2 n-1 3 // Insert A[j] into the sorted sequence A[1 .. j-1] 0 n-1 4 i = j-1 c4 n-1 5 while( i > 0 && A[i] > key) c5 6 { A[i+1] = A[i] c6 7 i = i-1 c7 8 } 9 A[i+1] = key c8 n-1 10 }