マージソートの計算量について-O(n*logn)

このQ&Aのポイント
  • マージソートの計算量はO(n*logn)ですが、その理由を理解することができません。
  • 要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となります。
  • 要素の比較コストが*nなのはなぜでしょうか。T(n)=2T(2/n)+O(n)という説明も理解できません。
回答を見る
  • ベストアンサー

マージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。 またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

質問者が選んだベストアンサー

  • ベストアンサー
  • mtaka2
  • ベストアンサー率73% (867/1179)
回答No.2

ソートの計算量を議論するときは、通常「比較回数」を考えます。 (正確には、全ての計算の手間を数えあげる必要がありますが、通常 ・計算処理の中で「比較回数」が最も多くなる ・計算量(オーダー)では次数の低い項は無視できる ので、比較回数以外は考える必要がなくなります) ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。 で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、 たとえば、16の要素をマージソートする場合を例にあげると、 ・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。 ・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。 ・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。 ・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。 以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。 この「比較回数」を「要素数n」の式で表現するわけですが、 個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、 総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1 になります。 計算量(オーダー)の議論では、次数の低い項は無視しますから、 O(n log n - n + 1) = O(n log n) になります。

redhat_001
質問者

お礼

ご丁寧な回答有り難うございました。

その他の回答 (1)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

なぜ「要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..とな」るのか説明してみてください.

redhat_001
質問者

補足

2/2=1 4/2/2=1 8/2/2/2=1 16/2/2/2/2=1 32/2/2/2/2/2=1 64/2/2/2/2/2/2=1

関連するQ&A

  • マージソートの計算量

    データ構造とアルゴリズムのテストでこんな問題が出てきました。 マージソートにおける値の比較回数は、C(n)は次のように表すことができる。C(4)は幾らか。 C(n) = 1 (n = 1のとき) C(n) = 2 C(n/2) + n (n > 1のとき) この問題の解答は12でした。 この問題を解くプロセスを教えていただけませんか? よろしくお願いします。

  • 挿入ソートとマージソート

    挿入ソートとマージソートの問題を解いているのですが、 途中で行き詰ってしまいました。 (問題文) サイズnの入力に対して、挿入ソートの実行には8n~2ステップかかり、 マージソートの実行には64nlnnステップかかる。 挿入ソートがマージソートに勝るnの値を求めよ。 補足:ln=eを底とするlog (挿入ソートがマージソートに勝る=挿入ソートがマージソートより実行時間が早い) 8n~2 <= 64nlnn 8lnn=n e~n=n~8 こういう感じで自分なりに考えてみたのですが、nの値をどのように出して良いのかわからず困っています。 どなたかご教授いただける方いましたらよろしくお願いします。

  • ソートの計算量などについて

    こんにちは ソートに関することの質問です。 1.バブルソートの計算量を出す式ですが O(n^2)=O(n-1)*O(n/2)*O(1)=O(n)*O(n)=O(n^2) で合っていますでしょうか? 2.クイックソートの(平均)計算量が nlog n(底は2)になるのは、なぜなのかを わかりやすく教えて下さい。(できれば式も) 3.クイックソートが最も高速に実行されるのは、ピボットの要素が真中にある場合で、反対に最も効率が悪いのはピボットが端にある場合ですが、この理由をやさしい言葉で教えて下さい。 どなたか教えて下さい。 よろしくお願いします

  • ソートプログラムで

    1.2つの配列a、bをマージする場合、比較回数が最大となる必要十分条件、最小となる必要十分条件 2.マージソートプログラムと選択ソートプログラムの比較回数について、要素数をnとしたときに、比較回数をnで表す にはどうしたらよいですか?初心者なので全然わかりません。教えてください。

  • マージソートの演算回数について

    授業でマージソートはn個の入力に対して、分割にかかる演算回数はlog n(底は2)であると言っていたのですが、どうしてなるかがどうしてもわかりません。 どなたかわかるかた、よろしくお願いします。

  • マージソート

    マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか? よろしくお願いします。 ~qtime.c~ //マージソート実行用プログラム //bcc32 mtime.c merge.c m1.c sfmt.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void merge_sort(int a[], int start, int end); main() { int i , x[MAX] , n; time_t start , end ; int sn; printf("適当な数字の入力 : "); scanf("%d", sn); init_gen_rand(sn); for(i=0; i<MAX; i++) x[i]= (gen_rand32()% MAX);; n=MAX; start = clock(); //測定対象プログラム merge_sort(x, 0, n-1); end = clock(); printf("sort\n"); for(i =0 ; i < n ; i++ ) if ( i == i/100*100) printf("%d\n" , x[i]); printf ("実行時間: %f sec\n" , (double)(end-start) /CLOCKS_PER_SEC); return 0; } ~merge.c~ int b[100]; void merge_array(int x[], int start, int end) { int mid, i, j, k; mid = (start + end) /2; i = start; j = mid + 1; for(k = start; k <= end; k++){ if(x[i] > x[j] && j <= end || i > mid){ b[k] = x[j]; j++; } else{ b[k] = x[i]; i++; } } for(k = start; k <= end; k++){ x[k] = b[k]; } } ~m1.c~ void merge_array(int x[], int start, int end); void merge_sort(int a[], int start, int end); void merge_sort(int a[], int start, int end) { int mid; if(start >= end) return; mid = (start + end) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge_array(a, start, end); }

  • マージソートについて

    void mergesort (int n, int x[]) { int i,j,k,m; if(n<=1) return; m=n/2; ここで分割するのは分かるのですが mergesort(m,x);      再帰させてなんでこの式でブロックを mergesort(n-m,x+m);    前半と後半に分けれるのか、分かりま                  せん。だれか教えてください!(><)

  • modified bubble sort

     ソーティングについて教えてください.  ソーティングの手法に,バブルソートというものがあります(隣接するふたつを入れ替える).このソーティングでは,最大交換回数は要素数が n のとき, n(n-1)/2 となります.  隣接する要素の交換に加え,先頭と最後の要素の入れ替えも可能だとすると(イメージとしては,サイクリックなバブルソートです),最大交換回数は n^2/4 となるそうです.  この n^2/4 になる,という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます).どなたかご教授頂ければと思います.

  • 多層マージソートが分かりません

    (1)テープを4本用いる多層マージソートでは初期連を3本のテープに  どう分配すればよいでしょうか? (2)テープ3本のとき(p=2)  F0=0 F1=1 Fn+1=Fn+Fn-1(n≧1)  総数 tn=2Fn+Fn-1を  Fn/tn:(Fn+Fn-1)/tnに分配すればよく、  この比はn→大のとき0.382:0.618に近づきます。  この収束の様子を観察するにはどのようなプログラムを  書けばよいでしょうか? (3)また、p=3のとき  F0=F1=0 F2=1 Fn+1=Fn+Fn-1+Fn-2(n≧2)  総数 tn=3Fn+2Fn-1+Fn-2を  Fn/tn:(Fn+Fn-1)/tn:(Fn+Fn-1+Fn-2)/tn  に分配すればよいです。  これを、一定精度に収束するnまで計算するには、  どのようなプログラムを書けばよいでしょうか? まだプログラムに不慣れですがプログラムしなければ ならなくなって困っています。 また多層マージソートについて分かりやすく詳しく説明 しているサイトがありましたら教えてください。

  • ソートに関する計算量について。

    処理時間Tが、それぞれT=5N            T=Nの2乗/10            T=Nlog2N (←log2の2は小さい2) の3つのプログラムがあります。 ここでNはプログラムで処理されるデータ数であります。 これらのプログラムのデータ数と処理時間について比較考察をせよ という問題があるのですが分かりません。 教えてください! お願いします!