삽입 - 정렬의 실행 시간

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 번은 아닌가? C에서 for 루프의 관점에서 그것에 대해

Answer 1

생각 :이 줄은 N 시간에 도달

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

- 한 번 초기화를 위해, 그리고 N-1 배 증가 앤 위해 테스트.

Answer 2

글쎄 내 관점에서 여분의 1 시간 비용 실제로 초기화되지 않은 이유는 n-1 성공적인 반복 제어가 i < = (길이 (A)) 조건으로 되돌아 가서 i를 A의 길이와 비교하기 때문입니다 이 1 개의 추가 비용은 루프에 추가됩니다.

이 내용은 페이지 번호에 설명되어 있습니다. Cormen의 알고리즘 소개 25.