誰かがこの問題の解決策を私に説明できますか？
ソートするn個の要素のシーケンスが与えられたとします。入力シーケンスは、それぞれがk個の要素を含むn=k個のサブシーケンスで構成されます。特定のサブシーケンスの要素はすべて、後続のサブシーケンスの要素よりも小さく、前のサブシーケンスの要素よりも大きくなります。したがって、長さnのシーケンス全体をソートするために必要なのは、 n=k個のサブシーケンスのそれぞれでk個の要素をソートすることだけ です。ソート問題のこの変形を解決するために必要な比較の数のnlgk下限を示します。
解決：
Sを、それぞれ長さkのn / k個のサブシーケンスに分割されたn個の要素のシーケンスとし ます。ここで、任意のサブシーケンスのすべての要素は、先行するサブシーケンスのすべての要素よりも大きく、後続のサブシーケンスのすべての要素よりも小さくなります。
請求
Sをソートするための比較ベースのソートアルゴリズムは、最悪の場合（n lg k）の時間がかかる必要があります。
証拠
ヒントで指摘されているように、各サブシーケンスをソートするための下限を乗算しても下限を証明できないことに最初に注意してください。これは、サブシーケンスを独立してソートするより高速なアルゴリズムがないことを証明するだけです。これは私たちが証明するように求められたものではありませんでした。追加の仮定を導入することはできません。
ここで、Sの比較ソートの高さhの決定木を検討します。各サブシーケンスの要素は任意の順序である可能性があるため、k！順列は、サブシーケンスの最終的なソート順に対応します。また、そのようなサブシーケンスはn / k個あり、それぞれの順序は任意であるため、入力順序の並べ替えに対応できるSの（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が奇数の場合は、床と天井で調整できます。）
少なくとも（n / 2）lg（k / 2）の長さのSをソートするための決定木には少なくとも1つのパスが存在するため、Sの比較ベースのソートアルゴリズムの最悪の場合の実行時間は（n lg k）。
誰かがコードブロックの手順を教えてもらえますか？特にlgkのときのステップ！lg（（k / 2）^ k / 2）になります。