2

これは、Introduction to Algorithms By Cormen からの質問です。しかし、これは宿題ではなく自習です。

length の配列がありnます。n/kそれぞれの長さのサブリストkが挿入ソートを使用してソートされ、マージメカニズムを使用してマージされるマージソートへの変更を検討してください。ここで、k は決定される値です。

nとの関係kは不明。配列の長さは ですn。平均kのサブリストは、配列の要素と等しくなります。したがって、マージソートで使用するための配列の分割が停止され、代わりに、定数係数が小さいため挿入ソートが使用されるという単純な制限があります。n/kn * (n/k)nk

Θ(n*k + n*lg(n/k))修正されたアルゴリズムが最悪の場合でも機能するという数学的証明を行うことができました。さて、本は続けてこう言いました

kの関数として、nこの修正されたアルゴリズムの実行時間が標準のマージ ソートと同じになるようなの最大値を Θ 表記で見つけます。実際には k をどのように選択すればよいでしょうか?

今、これは私に多くの時間を考えさせましたが、何も思いつきませんでした. 解いてみました

n*k + n*lg(n/k) = n*lg(n)関係のために。2 つの実行時間の同等性を見つけると制限が得られ、単純な試行錯誤を使用してそれ以上を確認できると思いました。

私はこのようにそれを解決しました

n k + n lg(n/k) = n  lg(n)

k + lg(n/k) = lg(n)

lg(2^k) + lg(n/k) = lg(n)

(2^k * n)/k = n

2^k = k

しかし、それは2 ^ k = k何の関係も示さない私に与えました。関係は何ですか？関係を見つけるための方程式を間違っていたのではないかと思います。

私はアルゴリズムを実装することができ、挿入ソートを呼び出すために関数here (マージソート実装の Github リンク) にif (length_Array < k)ステートメントを追加するだけで十分だと思います。しかし、実際の生活ではどのように選択すればよいでしょうか。merge_sortk

4

2 に答える 2

2

これは数学的最小化問題であり、それを解くには基本的な計算が必要です。

kwhichの値を見つける必要がありますd[n*k + n*lg(n/k)] / dk == 0。

k == n、およびであるエッジケースも確認する必要がありk == 1ます。

kの最小結果を与えるの値の候補はn*k + n*lg(n/k)、必要な範囲の最小値であり、したがって の最適値ですk。

添付ファイル、微分方程式を解く:

d[n*k + n*lg(n/k)] / dk = d[n*k + nlg(n) - nlg(k)] / dk
= n + 0 - n*1/k = n - n/k 
=>
n - n/k = 0 => n = n/k => 1/k = 1 => k = 1

ここで、候補があります: k=n, k=1. k=n の場合、 が得られるため、最適であるO(n^2)と結論付けます。kk == 1

必要な定数を使用する正確な複雑度関数ではなく、大きなシータからの関数で導関数が見つかったことに注意してください。
すべての定数を使用して正確な複雑さの関数でこれを行うと、最終結果が少し異なる可能性がありますが、それを解決する方法はほとんど同じで、別の関数からの導関数のみを使用します。

于 2013-08-07T13:18:52.053 に答える