- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
657 ：デフォルトの名無しさん[]：2017/10/15(日) 10:39:26.70 ID:Cy7I/MU1 - ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、
ちょうど n! 個と書かない理由は何ですか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
658 ：デフォルトの名無しさん[]：2017/10/15(日) 10:46:56.72 ID:Cy7I/MU1 - 既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの
ことを想定しているのでしょうか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
659 ：デフォルトの名無しさん[]：2017/10/15(日) 10:48:49.83 ID:Cy7I/MU1 - そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが
存在することになります。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
660 ：デフォルトの名無しさん[]：2017/10/15(日) 10:49:46.78 ID:Cy7I/MU1 - ソートの決定木について厳密に論じている本はありますか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
661 ：デフォルトの名無しさん[]：2017/10/15(日) 11:09:38.82 ID:Cy7I/MU1 - This result serves as a guide for us to know, when designing a sorting algorithm, how
well we can expect to do. For example, without such a result, one might set out to try
to design a compare-based sorting algorithm that uses half as many compares as does
mergesort, in the worst case. The lower bound in Proposition I says that such an effort
is futile?no such algorithm exists
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
662 ：デフォルトの名無しさん[]：2017/10/15(日) 11:10:24.51 ID:Cy7I/MU1 - >>661
この説明は間違っていますよね？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
663 ：デフォルトの名無しさん[]：2017/10/15(日) 11:13:29.73 ID:Cy7I/MU1 - 最悪時にマージソートの半分の比較しか必要でないソートのアルゴリズムが存在しないこと
は証明できるのでしょうか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
664 ：デフォルトの名無しさん[]：2017/10/15(日) 11:54:45.59 ID:Cy7I/MU1 - あ、勘違いしました。
>>661
合っていますね。明らかに。
|
|