-1

メソッドの実行時の複雑さを計算する最良の方法は何ですか? これは、バブルソートのような非再帰的な方法で簡単に実行できます

outer-for loop
{
   inner-for loop
      {
           compare and exchange
      }
}

確認するには、最も内側のループにカウンターを配置するのが最善の方法です。しかし、メソッドが再帰的である場合、カウンターをどこに置くべきか、たとえばマージソート、

sort(int[] array){

    left = first-half
    right = second-half

    sort(left);
    sort(right);
   ret merge(left, right);

}

merge(int[] left, right)
{
    count = length(left + right);
    int[] result;
    loop-count-times
    {
       compare and put in result;
    }

  return result;
}

これはマージソートであるため、big(o) は o(n log n) であるため、100 int の配列は正確に 200 の big-o を返す必要があります。カウンターはどこに行くの？sort(..) の一番上に置くと、平均は 250、280、300 になりますが、これは間違っているはずです。このカウンターの最適な場所はどこですか?

参照: http://en.wikipedia.org/wiki/Mergesort

ありがとう。

4

2 に答える 2

2

これはマージソートであるため、big(o) は o(n log n) であるため、100 int の配列は正確に 200 の big-o を返す必要があります。

右寄りでもない。

大きな Ordo 表記法を使用して示される計算の複雑さは、正確に実行されるステップ/計算操作の数を示しません。それが漸近的で同一の複雑さではないと呼ばれる理由があります.入力のサイズに関してアルゴリズムの実行時間に近づく（より正確には、より高い境界を与える）関数のみを提供します。

つまりO(n log n)、100 個の要素に対して 200 回の演算が実行されるという意味ではありません (ちなみに、対数の底が 10 でなければならないのはなぜですか? )。入力のサイズを大きくすると、( average-case) 実行時間は、追加された入力データの数に、この追加データの数の対数を掛けたものに比例します。

要点: 再帰関数の呼び出し回数をカウントしたい場合は、次のようにカウンターを引数として入れる必要があります。

void merge_sort(int array[], size_t length, int *counter)
{
    (*counter)++;
    // apply the algorithm to `array`:
    merge_sort(array, length, counter);
}

次のように呼び出します。

int num_calls = 0;
merge_sort(array, sizeof(array) / sizeof(array[0]), &num_calls);
printf("Called %d times\n", num_calls);
于 2013-03-10T06:40:12.980 に答える
1

Big-O表記の概念を少し誤解していると思います。複雑度が O(n log n) で n の値が 100 の場合、プログラムを 200 の Big-O で正確に実行する必要があるという厳密な規則はありません。これは上限を与えるだけです。たとえば、O(n 2 ) の複雑さを持つ選択ソートを考えてみましょう。n が 100 であっても、リストが既にソートされている場合、内側のループ内に設定されたカウンターは結果として 100 2を与えません。したがって、あなたの場合、答えとして得られるもの (250、280、300 など) は完全に有効です。すべての答えは、k × n log n によって制限されるためです。ここで、k は任意の定数です。

于 2013-03-10T06:37:16.127 に答える