0

挿入ソート用に以下のコードを作成しました。従来のアプローチの代わりに、関数呼び出しを使用してコードを記述することにしました。しかし、コードの複雑さを見つけることができません。時間と空間の複雑さと、従来のアプローチとの違いを見つけるのを手伝ってください。

#include <stdio.h>

void printArray(int ar_size, int *  ar){
    int j;
    for(j=0; j<ar_size; j++)
                printf("%d ", ar[j]);

        printf("\n");
}
void insertion(int ar_size, int *  ar, int p) {
    int last = p, j;
    int v = ar[last];

    for(int i=last; i>=0; i--){
        if(ar[i-1] > v){
            ar[i] = ar[i-1]; 
        }
        else{
            ar[i] = v;
            break;
        }     
    }
    printArray(ar_size, ar);
}

void insertionSort(int ar_size, int *  ar) {
    int i;
    for(i=1; i<ar_size; i++){
        insertion(ar_size, ar, i);
    }
}

int main(void) {

   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size, _ar);

   return 0;
}

以下は、挿入ソートの従来のアプローチです。

void InsertionSort(int a[], int n)
{
    int i,j, temp;
    for(i=0; i<=n-1; i++)
    {
        temp = a[i];
        j = i;
        while(a[j-1] > temp && j>=1)
        {
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }   
}
4

1 に答える 1

0

コードの時間計算量はまだ O(n²) です。for ループの内部をinsertion関数に移動しても、複雑さは変わりません。関数の内容をそれを呼び出すループにコピー アンド ペーストしてinsertionも、コードの実行時間に違いはありません (実際、コンパイラは最適化の一環として、コンパイル時にこれを正確に実行します)。

このようにコードを見ると、提供した参照コードと本質的に機能的に同等であることがわかります。

  1. 参照コードには、0 から配列サイズまでの外側のループがあります。
  2. 参照コードの内側のループは、配列内の現在の位置から先頭までループするか、より小さい要素が見つかるまでループします。あなたのコードは、より多くのコード行で、まさにこれを行う関数を呼び出します。

機能的には、コードは参照挿入ソートの実装と本質的に同じです。どちらも同じ時間の複雑さを持ち、まったく同じ一連の手順で配列をソートします。ただし、参照実装は、変数の代入をあまり行わず、関数呼び出しを使用しないため、わずかに高速になる可能性があります。

最適化を有効にして (デフォルトで) コンパイルすると、両方のコードがほぼ同じになります。

于 2015-05-23T08:13:55.237 に答える