4

アルゴリズムの本から練習をしなければなりません。0.1から0.9の範囲のαで配列を分割するマージソートが実装されているとします。

これは、分割点を計算するための独自の方法です

middle = fromIndex + (toIndex - fromIndex)/2;

これに変更したいと思います：

factor = 0.1; //varies in range from 0.1 to 0.9
middle = fromIndex + (toIndex - fromIndex)*factor;

だから私の質問は：

  1. これは計算の複雑さに影響しますか？
  2. 再帰ツリーの深さにどのような影響がありますか？
4

1 に答える 1

4

これは実際の複雑さを変更しますが、漸近的な複雑さは変更しません。

あなたが得る新しい漸化式について考えるならば、それは

T（1）= 1

T（n）= T（αn）+ T（（1-α）n）+Θ（n）

再帰ツリーを見ると、ツリーの各レベルには、レベルごとに合計Θ（n）の作業がありますが、レベルの数は多くなります。具体的には、0.5≤α<1であると仮定します。次に、k回の再帰呼び出しの後、再帰に残っている最小のブロックのサイズはサイズnαkになります。これがサイズ1に達すると、再発は停止します。解くと、次のようになります。

nαk = 1

αk =1/ n

klogα=-logn

k = -logn/logα

k = log n / log（1 /α）

言い換えると、αを変化させると、再帰の深さの対数項の定数係数が変化します。上記の式は、α= 0.5のときに最小化されます（α≥0.5の制限を受けるため）。したがって、これが最適な分割方法になります。ただし、他の分割を選択すると、定数項は高くなりますが、実行時のΘ（n log n）が得られます。

お役に立てれば！

于 2013-02-04T18:00:33.637 に答える