マージソートの計算量は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)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。
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) になります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- お酒・アルコール 高学歴の女性は飲酒率が高いという仮説は本当だと思いますか? 5 2022/08/11 11:33
- その他(保険) 投資目的の保険商品について。受取時にかかる税金について保険会社に質問しました。 商品を端的に説明する 3 2023/08/08 20:33
- 数学 情報処理詳しい人!! A4縦のレポート文書に4:3の大きさの横向きの写真画像を貼り付けることにした。 2 2022/12/18 02:30
- 哲学 説得力を修辞の巧みさまたは論理の強さの2つに分析するにはどうすると良いでしょうか? 0 2022/07/20 05:46
- 教育学 学校ってなんで必要? 8 2022/08/24 19:36
- 統計学 t検定を繰り返してはいけない理由について教えて下さい。 2 2022/05/15 12:37
- 物理学 物理の証明問題についての質問です。 平面内を運動する小球がある。この物体にかかる加速度の方向と大きさ 2 2023/05/16 00:28
- 発達障害・ダウン症・自閉症 とても悩んでる事があります。それは根本的に頭が悪い事です。 先ほどこのようなテレビ番組で、説明があっ 2 2022/10/02 11:30
- 仕事術・業務効率化 上司の人の仕事内容の説明が早すぎてついていけません。 1 2022/12/02 12:41
- オープンソース IT用語、ソースとオブジェクト、改変と翻訳と翻案の違いなど どのようにりかいすればよいのですか 1 2022/09/09 10:02
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
2個のFormを横並びにしたい
-
NからZへの全単射を具体的に構...
-
含む含まないという概念自体の...
-
border: noneでボタンの境界線...
-
質問1.
-
smallにtext-allignが効かない
-
超音波で洗脳。
-
input type="hidden"で取得した...
-
タグ前後で自動改行されない
-
改行ほどは行かないけど、若干...
-
【 Python range関数とlen関数 】
-
スタイルシートで文字色を指定...
-
CSS:overflow要素の印刷について
-
listでもっぱら通常iteratorを
-
自然数と偶数の自然数は全単射...
-
<div align="center">を使わず...
-
テーブルタグを使わない、表作り。
-
CSSで改行後の行間調整
-
figcaption要素の中にul要素
-
【ヒトの神秘】美男美女から何...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
【ヒトの神秘】美男美女から何...
-
2個のFormを横並びにしたい
-
含む含まないという概念自体の...
-
角丸画像の背景色を透明にした...
-
smallにtext-allignが効かない
-
超音波で洗脳。
-
質問1.
-
「諸要素」とはどういう意味で...
-
改行ほどは行かないけど、若干...
-
1から100までの自然数のうち、2...
-
マージソートの計算量について-...
-
タグは大文字と小文字どちらが...
-
textareaの幅を画面と合わせたい
-
親要素・子要素
-
テキストボックスの中にリンク...
-
html タグの閉じスラッシュ前の...
-
input type="hidden"で取得した...
-
NからZへの全単射を具体的に構...
-
【CSS】imgタグを、親要素の幅...
-
HTMLページ上でiframeを最前面...
おすすめ情報