デシジョンツリー解決する問題

Question

私はデータ構造に関する試験を受けており、決定木（nlog n W.Cの最小値でn個の要素をソートする）を使って解決された問題を全面的に見てきました。 誰かが私にそのような質問のための情報源を提供できるなら、私は満足しています。 ありがとうございます。

もちろん

Answer 1

、あなたは1〜1024の間の数を推測しなければならないときのケースを考えると、あなたが推測したときに、二つの可能性があります。

1. あなたは右のそれを推測。
2. あなたは間違っていると推測しました。

1.の場合、答えが見つかりましたので、アルゴリズムは終了します。 2.の場合、さらに決定があります。

2.1。あなたが探している数字は、あなたの推測である 2.2より小さいです。あなたが探している番号を使用すると、バイナリ検索をモデル化する場合は、有限回数のために非常に同じ考えを繰り返すことになりますように、そしてあなたの仕事は、非常にシンプルになり、

だからあなたの推測よりも大きくなります。バイナリ検索の詳細については、こちらをご覧ください：

https://en.wikipedia.org/wiki/Binary_search_algorithm