셸 정렬의 시간 복잡도

Question

버블 정렬 및 삽입 정렬과 비교할 때 셸 정렬에서 시간 복잡성이 적은 이유는 무엇입니까? 우리는 어떻게 시간 복잡성을 계산할 수 있습니까? 즉, 우리는 어떤 기준에서 우리 코드가 높거나 낮은 시간 복잡성이라고 생각합니까? 우리는 우리의 코드가 높거나 낮은 시간 복잡도 N 요소와 알고리즘을 정렬 고려하는 간단한 일이 생각 무엇을 기준으로 귀하의 질문에 에 대해서는

는

#include <stdio.h> 
void shellsort(int arr[], int num) 
{ 
    int i, j, k, tmp; 
    for (i = num/2; i > 0; i = i/2) 
    { 
     for (j = i; j < num; j++) 
     { 
      for (k = j - i; k >= 0; k = k - i) 
      { 
       if (arr[k + i] >= arr[k]) 
        break; 
       else 
       { 
        tmp = arr[k]; 
        arr[k] = arr[k + i]; 
        arr[k + i] = tmp; 
       } 
      } 
     } 
    } 
} 
int main() 
{ 
    int arr[30]; 
    int k, num; 
    printf("Enter total no. of elements : "); 
    scanf("%d", &num); 
    printf("\nEnter %d numbers: ", num); 
    for (k = 0; k < num; k++) 
    { 
     scanf("%d", &arr[k]); 
    } 
    shellsort(arr, num); 
    printf("\n Sorted array is: "); 
    for (k = 0; k < num; k++) 
     printf("%d ", arr[k]); 
    return 0; 
} 

Answer 1

많은 비교가 정렬 된 요소의 배열을 만들기 위해 만들어진 방법이다. 이러한 비교로 인해 요소 교환이 이루어 지므로 시스템 (CPU)에 사용되는 리소스가 늘어납니다.

버블/삽입 정렬은 n^2 비교로 끝날 수 있습니다 (스왑을 만들지 않으면 최적화 할 수 있고 정렬 된 배열은 다시 스캔하지 않을 수 있습니다). 셸 정렬은 특정 시나리오에서 n^2보다 좋게 개선되었습니다. 위키 백과 포인터는 좋은 참고 자료이지만 알고리즘에 대한 책을 읽고 명확하게 처리하는 방법을 설명합니다 (데이터 구조 및 알고리즘 분석 - Mark Allen Weiss 또는 일부)