셸 정렬 알고리즘의 실행 시간을 계산하는 방법

Question

셸 정렬 알고리즘의 실행 단계를 단계별로 계산하는 방법?

shellsort(itemType a[], int l, int r){ 
    int i, j, k, h; 
    itemType v; 
    int incs[16] = { 1391376, 463792, 198768, 86961, 33936, 
        13776, 4592, 1968, 861, 336, 
        112, 48, 21, 7, 3, 1 }; 
    for (k = 0; k < 16; k++) 
    { 
     for (h = incs[k], i = l+h; i <= r; i++) 
     { 
     v = a[i]; j = i; 
     while (j >= h && a[j-h] > v) 
     { 
      a[j] = a[j-h]; 
      j -= h; 
     } 
     a[j] = v; 
     }//end inner-for loop 
    }//end outer for-loop 
}//end shellsort 

Answer 1

위키 백과는 O (N 특급 (N SQRT (8 로그 (5/2) 로그()))의 경계와 Incerpi과 세지에 의해 종이로 안내하고있다. 나는 당신이 거기 보면 좋을 것 많은 shellsort 변종의 런타임에 좋은 범위를 얻는 것은 매우 중요하지 않습니다. 아마도 이것을 포함해서