このソリューションの問題の決定木の例はありますか。
質問に応じて決定木を描きたいと思います（ほとんどの人が理解できるように）。しかし、この決定木の描き方がわかりません。例として、このアルゴリズムの表現に葉が使用されているかわかりません
質問2
n 個の赤と n 個の青の水差しが与えられたとします。すべて形状とサイズが異なります。青い水差しと同様に、赤い水差しはすべて異なる量の水を保持します。さらに、すべての赤いジャグには、同じ量の水が入る青いジャグがあり、その逆も同様です。
あなたの仕事は、同じ量の水を保持する赤と青の水差しのペアに水差しのグループを見つけることです. これを行うには、次の操作を実行できます。1 つは赤でもう 1 つは青の水差しのペアを選び、赤の水差しに水を入れてから、水を青の水差しに注ぎます。この操作により、赤または青のジャグがより多くの水を保持できるかどうか、または同じ容量であるかがわかります。このような比較には 1 時間単位かかると仮定します。あなたの目標は、グループ化を決定するための最小数の比較を行うアルゴリズムを見つけることです。2 つの赤い水差しや 2 つの青い水差しを直接比較しないでください。
1. Θ(n2) 比較を使用して水差しをペアにグループ化する決定論的アルゴリズムを説明してください。2. この問題を解くアルゴリズムが行う必要のある比較回数の Ω(nlgn) の下限を証明してください。
この問題を解決するには、一致を判断するのに十分な情報が得られるまで、アルゴリズムで一連の比較を実行する必要があります。決定木の観点からアルゴリズムの計算を見ることができます。すべての内部ノードには、比較する 2 つのジャグ (1 つは赤、もう 1 つは青) のラベルが付けられており、3 つの発信エッジ (赤のジャグは小さい、同じサイズ、または青いジャグよりも大きい) があります。葉は水差しのユニークなマッチングでラベル付けされています。第 8 章の解決策: 線形時間での並べ替え 8-17 決定木の高さは、一致を判断するためにアルゴリズムが行わなければならない最悪の場合の比較回数に等しくなります。そのサイズを制限するために、最初に n 個の赤と n 個の青の水差しの可能な一致の数を計算しましょう。比較を開始する前に、赤色の水差しに 1 から n までのラベルを付け、青色の水差しにも 1 から n までのラベルを付けると、アルゴリズムのすべての結果は、セット {(i,π(i)) : 1 ≤ i ≤ n として表すことができ、π は {1,..., n}} の順列であり、赤い水差しのペアが含まれています。 (第 1 コンポーネント) と青い水差し (第 2 コンポーネント) が一致します。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。これには、一致する赤の水差し (最初のコンポーネント) と青の水差し (2 番目のコンポーネント) のペアが含まれています。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。これには、一致する赤の水差し (最初のコンポーネント) と青の水差し (2 番目のコンポーネント) のペアが含まれています。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。