誰かが私にこの問題の解決方法を説明できますか？比較ソート - 理論的
並べ替えの対象となる要素がnとなっているとします。入力シーケンス は、n = kサブシーケンスで構成され、それぞれがk要素を含んでいます。与えられた サブシーケンス内の要素はすべて、後続のサブシーケンス内の要素より小さく、前のサブシーケンス内の要素よりも大きい です。したがって、すべてのことは ソートNがN = K サブシーケンスの各々におけるK要素をソートする長さのシーケンス全体に必要とされます。ソート問題のこの変形を解決するために必要とされる比較数の下限を ng 0と表示してください。
対処：
Sは、に分割N要素のシーケンスN/Kサブ配列長K任意のサブシーケンス内のすべての要素がすべてより大きい の各ことう前のサブシーケンスの要素 は、後続のサブシーケンスの要素のすべてよりも小さい。
項
任意の比較に基づくソートアルゴリズムは 最悪の場合時間（N LGのk）を取らなければならないSをソートします。
証明
ヒントに指摘したように、我々は 下の各サブシーケンスをソートするための下限を一緒に乗じて拘束さを証明することができない、という最初の通知。 これは、部分配列 を独立してソートする高速アルゴリズムがないことを証明するだけです。これは私たちが証明することではありませんでした。余計な前提を導入することはできません。今
各サブシーケンスの 要素はkのいずれかの、任意の順序にすることができますので、S.のための任意の比較の並べ替えのための高さhの決定木を考えます！順列 は、サブシーケンスの最終ソート順に対応します。また、n/kのような サブシーケンスがあり、それぞれが任意の順序であることができるので、いくつかの入力順のソートに対応できるSの の順列が存在する。したがって、Sをソートするための任意の決定 ツリーは少なくとも（k！）^ n/kの葉が必要です。高さのバイナリツリー時間 がせいぜい2^Hの葉を持っていないので、我々は2^H≥（K！）^（N/K）または時間≥の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が偶数であることをここで仮定する。）
をで長 を有するSをソートするための任意の意思決定ツリー内の少なくとも1つの経路が存在するので最小の（n/2）lg（k/2）の場合、Sに対するアルゴリズムベースの比較の最悪ケース実行時間は（nlg k）です。
誰かがコードブロックの手順を教えてくれますか？特にステップがlg k！はlg（（k/2）^ k/2）になります。
Iは、以下の数学を転載しまし
私の疑問は、ステップ2から3に向かいました。ありがとうございました！ – Zombie