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

2008/10/15 17:21

この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)という説明も理解できません。

redhat_001
お礼率75% (42/56)

C・C++・C#
回答数2
ありがとう数7

みんなの回答 （2）
専門家の回答

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

ベストアンサー

mtaka2
ベストアンサー率73% (867/1179)

2008/10/15 18:03 回答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) になります。

質問者