時間複雑ソート

Question

？時間の複雑さを計算するにはどうすればいいのですか。

#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

我々は我々のコードを考えるもの基づいてあなたの質問に関して高いまたは低い時間計算であるN個の要素を持つアルゴリズムをソートするために考慮すべき単純なことは、ソートされた要素の配列を作るために作られていますどのように多くの比較です。比較は、さらに、システム（CPU）上で使用されるより多くのリソースに変換素子のスワップにつながります。

バブル/挿入ソートは、（何スワップは、次にソート済みアレイに再度スキャンしない行われていない場合に最適化することができる）、N^2つの比較で終わることができます。特定のシナリオでは、シェルソートはn^2よりもうまくいくように改良されました。ウィキペディアポインタは良い参考ですが、特に、より明瞭得るためにソートを扱うアルゴリズムについての本読ん示唆している - のhttpsこれを読んで