2

ねえ、複雑さを判断するのを手伝ってくれる人がいますか?. 私のクラスで与えられた例は

バブルソート

int main() {
   int a[10] = {10,9,8,7,6,5,4,3,2,1};
   int i,j,temp;

   for (j=0;j<10;j++) {
      for (i=0;i<9;i++) {
         if (a[i] > a[i+1]) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
         }
      }
   }
   for (i=0;i<10;i++) {
      printf("%d ",a[i]);
   }
}

O(n) のループが 2 つあるため、O(n^2) の複雑さがあり、O(n) x O(n) でした。

彼らは、クイックソートには O(nlog(n)) の複雑さがあると言いました..これはなぜですか?

ループを回って数を割るからですか？

-ありがとう

4

7 に答える 7

9

簡単な一文の説明はありません。クイックソートは実際最悪O( n 2 )ですが、平均するとO( n log n )なので、解析しようとすると必ずO( n log n )とは証明できません。可能なすべてのデータセットで平均すると、平均で O( n log n )しかありません。特定のリストについては、さらに悪い可能性があります。

ピボットが非常に悪い場合、クイック ソートのパフォーマンスは非常に悪くなります。これは、たとえば、配列の先頭または末尾にある固定要素をピボット要素として常に選択した場合など、既に並べ替えられたデータで発生する可能性があります。

一方、マージ ソートやヒープ ソートなどの他のソート アルゴリズムは、常に O( n log n ) です。パフォーマンスが O( n 2 )に低下する病理学的なケースはありません。これにより、常に一貫した予測可能なパフォーマンスが必要な場合に適しています。クイックソートの利点は、全体的に平均して高速なアルゴリズムであることですが、常にそうであるとは限りません。

編集: 実際、@pstが言うように、マージ ソートは、配列をソートするときに O( n ) スペース (マージ用のスクラッチ スペース) を必要としますが、これは理想的ではありません。それはそれに対するポイントです。しかし、クイック ソートに対するもう 1 つのポイントは、それが不安定なソートであることです。互いに等しい要素は、並べ替え後にシャッフルされる場合があります。

Timsortはすばらしい新しい検索アルゴリズムです。新しいものというよりは、既存のアルゴリズムの優れた組み合わせに加えて、多くの微調整と巧妙な最適化が行われています (疾走するのはお金です)。そのテキスト ファイルを読んで、優れたプログラミングを垣間見ることができます。

于 2009-10-28T03:12:23.103 に答える
4

Big-O表記法は、入力値（あなたの場合は要素数）と複雑さ（あなたの場合は時間の複雑さ、空間の複雑さでもある）との間の単純な関係です。

あなたはバブルソートについて正しいです。n時間の別のループ内で時間をループするためn、時間の計算量は O(n 2 ) です。

クイックソートは少し異なります。依存するパスの数を実行しますnが、それぞれの場合に、「左」の中間点よりも低いすべての値と「右」の中間点よりも高いすべての値を配置することができます-両方の半分はまだソートされていませんが、すべての左側の要素が右側のどの要素よりも少ないことがわかっています(これをピボット ルールと呼びましょう)。

これにより、基本的に各サブループのワークロードが半分になり、平均ケース O(log n) になります。二分探索やバランス ツリーと同様に、ワークロードを各反復の係数で分割するアルゴリズムは O(log n) です。

2 つを組み合わせると、O(n log n) が得られます。

このウィキペディアのページでは、実際に右上にクイックソートの動作を示す素敵な小さなグラフィックが表示されます。1 枚の絵は 1,000 語に匹敵する (そしてアニメーションは 1,000 枚の絵に匹敵する) ため、理解するにはしばらくそれを見てください。

最初にワークスペースを 2 つに分割し、ピボット ルールが満たされるまで 2 つの半分の間で要素を交換することがわかります。

ワークロードは完全に独立した 2 つの領域に分割されるため、クイックソートはリソース競合のない並列処理に最適です。十分なプロセッサがある場合、データを 2 つの領域に分割したらすぐに、各領域を別のプロセッサに割り当てて、さらに分割することができます。バブル ソートでは 2 つの独立した領域が得られないため、これは不可能です。

于 2009-10-28T03:16:14.123 に答える
2

実際、クイックソートは平均的な場合O（n log（n））です。最悪の場合、毎回最大または最小の要素をパーティションとして選択し、n +（n -1）+ ... 1 = O（n ^ 2）を実行します。

最良の場合（平均的な場合は同じbig-Oで動作します）、最初のパーティションに対してn回の比較を行います。これにより、サイズn / 2の問題に対して2つの呼び出しが行われ、それらの呼び出しはパーティションに対してn/2の比較を行います。これは続くので、n + 2 *（n / 2）+ 4 *（n / 4）+...を取得します。log（n）の合計項があり、それぞれがnであるため、全体がO（n * log（n））になります。

トーンが言ったように、マスターの定理を適用しても同じ結果を得ることができますが、手作業でいくつかの例を実行することはおそらく時間の価値があります。

于 2009-10-28T03:23:57.827 に答える
2

ウィキペディアの分析を参照してください。

于 2009-10-28T03:10:29.117 に答える
0

クイックソートは再帰的です。疑似コードを書き出すだけで、繰り返しの実行時間ごとに再帰式を簡単に導き出すことができ、マスター定理を使用して最終的な答えにたどり着くことができます。

于 2009-10-28T03:10:58.553 に答える
-1

ここにいるすべての人の意見に反して、あなたのプログラムの複雑さは O(1) です。n が何であるかを定義していません。私の答えは少しばかげているように思えますが、実際には、アルゴリズムの複雑さよりも問題の境界を見つけることが重要な場合がよくあります。データセットが特定のサイズよりも大きくならない場合は、十分なパフォーマンス/動作を備えたより単純な方法を使用することをお勧めします。

于 2009-11-04T20:52:11.153 に答える