은 특정 삽입 정렬의 실행 시간을 결정합니다

Question

배열 길이가 n이라고 가정하면 배열은 첫 번째 인덱스부터 인덱스 t까지 부터 1과 0으로 배열됩니다. 인덱스 t + 1에서 n까지 , 오직 0입니다. 예 [1,1,1,1 ..., 1,0,0 ... 0,0,0]

삽입 용 정렬 알고리즘 :

InsertionSort(Input: integer n, array A) 
{ 
for j = 1 to n { 
newnum = A[j] 
i = j-1 
while (i > 0 and newnum < A[i]) 
{ 
A[i+1] = A[i] 
i = i-1 
} 
A[i+1] = newnum 
} 
} 

이것이 제가 지금까지 가지고있다 :

\ 합 _1^N : 왼쪽 (\ C1 + \ 합 _1^{NT} C2 : \ 오른쪽)

Answer 1

루프는 오른쪽에 제 0 이동하면서 내부 1의 왼쪽에있는 1의 목록입니다. t1s ~ 점프 이상이고, (n - t)0s가 모두 이동합니다.

따라서 t * (n - t)입니다.

배열의 첫 번째 0에 도달하는 데 걸리는 시간 동안 t을 추가하거나 추가하지 않을 수도 있습니다.