比較ソート - 理論

Question

誰かが私にこの問題の解決策を説明できますか？

あなたが一連のシーケンスを与えられていると仮定します n ソートする要素。入力シーケンスは次のとおりです n = k サブシーケンス、それぞれが含まれます k 要素。特定のサブシーケンスの要素はすべて、後続のサブセンセンスの要素よりも小さく、前のサブセンスの要素よりも大きくなります。したがって、長さのシーケンス全体を並べ替えるために必要なすべて n ソートすることです k それぞれの要素 n = kサブシーケンス。 show an n lg k ソート問題のこのバリアントを解決するために必要な比較の数の下限。

解決：

させて s シーケンスになります n に分かれた要素 n/k 長さの各シーケンス kここで、サブセンセンスのすべての要素は、先行するサブセンスのすべての要素よりも大きく、後続のサブセンスのすべての要素よりも小さくなります。

請求

ソートする比較ベースのソートアルゴリズム s 取る必要があります （n lg k） 最悪の場合の時間。

証拠

ヒントで指摘されているように、各サブセンスを並べ替えるための下限を掛けることで下限を証明できないことに最初に注意してください。それは、サブシーケンスを独立してソートするより速いアルゴリズムがないことを証明するだけです。これは私たちが証明するように求められているものではありませんでした。追加の仮定を導入することはできません。

ここで、各サブセンションの要素は任意の順序で、どのような順序である可能性があるため、Sの比較ソートについては、高さHの決定ツリーを検討してください。 k！ 順列は、サブシーケンスの最終的なソートされた順序に対応しています。そして、あるので n/k そのようなサブシーケンスは、それぞれが任意の順序である可能性があります、 （k！）^n/k いくつかの入力順序の並べ替えに対応できるSの順列。したがって、並べ替えの決定ツリーは少なくとも持っている必要があります （k！）^n/k 葉。高さのバイナリツリー以来 hそれ以上のものがありません 2^h 葉、私たちは持っている必要があります 2^h≥（k！）^（n/k） また H≥Lg（（k！）^n/k）. 。したがって、取得します

     h ≥ lg((k!)^n/k)          -- unbalanced parens - final one added?
       = (n/k) lg(k!)
       ≥ (n/k) lg((k/2)^k/2)
       = (n/2) lg(k/2)

3行目はから来ます k！ それを持っています K/2 少なくとも最大の用語 K/2 各。 （ここでは、kは均等であると暗黙的に想定しています。 k 奇妙でした。）

少なくとも長さの並べ替えのために、決定ツリーに少なくとも1つのパスが存在するため （n/2）LG（K/2）, 、sの比較ベースのソートアルゴリズムの最悪の実行時間は （n lg k）.

誰かがコードブロックのステップを私に歩かせることができますか？特にステップ LG K！ なります lg（（k/2）^k/2）.

Answer 1

以下で数学を転載しました：

（1）H≥LG（K！ ^n/k)

（2）=（n/k）lg（k！）

（3）≥（n/k）lg（（k/2）^K/2)

（4）=（n/2）lg（k/2）

これを歩きましょう。行（1）から行（2）に移動すると、対数のプロパティが使用されます。同様に、行（3）から行（4）に移動すると、対数のプロパティと（n / k）（k / 2）=（n / 2）のfacthのプロパティが使用されます。したがって、トリックステップは、行（2）からライン（3）に進むことです。

ここでの主張は次のとおりです。

すべてのk、k！ ≥（k / 2）^{（k / 2）}

直感的には、アイデアは次のとおりです。 Kを考えてみてください！ = k（k -1）（k -2）...（2）（1）。気付いた場合、これらの用語の半分はk / 2よりも大きく、それらの半分は小さくなります。 k未満のすべての用語をドロップすると、次のものが（近く）を取得します。

k！ ≥k（k -1）（k -2）...（k / 2）

今、私たちはそのk /2≥kを持っているので、私たちはそれを持っています

k！ ≥k（k -1）（k -2）...（k/2）≥（k/2）（k/2）...（k/2）...（k/2）

これは（k / 2）それ自体（k / 2）の産物であるため、（k / 2）に等しくなります^K/2. 。奇妙な値と偶数の値のロジックは少し異なるため、この数学は正確ではありませんが、本質的にこのアイデアを使用すると、以前の結果の証明のスケッチが得られます。

要約するには：（1）から（2）から（3）から（4）から（4）は、対数のプロパティを使用し、（2）から（3）から上記の結果を使用します。

お役に立てれば！