誰かが次の問題の解決策の数学的部分を教えてくれませんか。
実行時間がnの少なくとも半分で線形である比較ソートがないことを示してください！長さnの入力。長さnの入力の1/nの一部はどうですか？分数（1 /（2）^ n）はどうですか？
解決：
ソートがm個の入力順列に対して線形時間で実行される場合、m個の対応する葉とその祖先で構成される決定木の部分の高さhは線形です。定理8.1の証明と同じ引数を使用して、m = n！/ 2、n！/ n、またはn！/2nではこれが不可能であることを示します。2 ^h≥mであるため、h≥lgmになります。ここに示されているすべての可能なmsについて、lgm =Ω（nlg n）、したがってh =Ω（nlg n）です。特に、
lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1
lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n
lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n
これらの各証明は、Ω（n log n）よりも速くソートする比較ソートを使用できないというより一般的な証明を直接変更したものです（この証明は、この以前の回答で確認できます）。直感的には、議論は次のようになります。並べ替えアルゴリズムが正しく機能するためには、要素の最初の順序を判別できる必要があります。そうしないと、値を昇順に並べ替えることができません。n個の要素が与えられると、n個あります！それらの要素の異なる順列、つまりnがあります！ソートアルゴリズムへのさまざまな入力。
最初、アルゴリズムは入力シーケンスについて何も知らず、n！のいずれかを区別できません。さまざまな順列。アルゴリズムが比較を行うたびに、要素の順序についてもう少し情報が得られます。具体的には、入力順列が、比較でtrueが得られる順列のグループにあるのか、比較でfalseが得られる順列のグループにあるのかを判断できます。アルゴリズムがバイナリツリーとしてどのように機能するかを視覚化できます。各ノードはアルゴリズムのある状態に対応し、特定のノードの（最大）2つの子は、比較でtrueが得られた場合に入力されるアルゴリズムの状態を示します。またはfalse。
並べ替えアルゴリズムが正しく並べ替えられるようにするには、可能な入力ごとに一意の状態を入力できる必要があります。そうしないと、アルゴリズムが2つの異なる入力シーケンスを区別できず、少なくとも1つを並べ替えることになります。間違って。これは、ツリー内のリーフノード（アルゴリズムが比較を終了してソートしようとしている部分）の数を考慮する場合、入力順列ごとに少なくとも1つのリーフノードが必要であることを意味します。一般的な証明には、nがあります！順列なので、少なくともn個必要です。リーフノード。二分木では、k個のリーフノードを持つ唯一の方法は、少なくともΩ（log k）の高さを持つことです。つまり、少なくともΩ（log k）の比較を行う必要があります。したがって、一般的なソートの下限は、スターリングの近似によるΩ（log n！）=Ω（nlog n）です。
あなたが検討している場合、私たちはそれらの可能な順列のサブセットに自分自身を制限しています。たとえば、nを並べ替えることができるようにしたいとします。/順列の2。これは、ツリーの高さが少なくともlg（n！/ 2）= lg n！でなければならないことを意味します。-1 =Ω（nlog n）。結果として。線形関数がΩ（nlog n）の割合で成長しないため、時間O（n）で並べ替えることはできません。2番目の部分では、nを取得できるかどうかを確認します。/ nは線形時間でソートされます。ここでも、決定木は高さlg（n！/ n）= lg n！である必要があります。--lg n =Ω（nlog n）であるため、O（n）の比較で並べ替えることはできません。最後の1つは、そのlg nです！/ 2 n = lg n！--n =Ω（nlog n）であるため、O（n）時間でソートすることはできません。
ただし、 lg 2 n = n = O（n）であるため、線形時間で2nの順列を並べ替えることができます。
お役に立てれば！