为合并排序算法创建决策树
Creating a decision tree for the mergesort algorithm
在我的作业中，我需要为任意输入 S={a,b,c} 创建 n=3 的决策树。
这是我的递归调用树。
S={a,b,c} 变成 S={a} 和 S={b,c} 和 S={b,c} 变成 S={b} 和 S={c}。在基本情况下，我有 S={a}、S={b} 和 S={c}。
当我将 S={b} 与 S={c} 合并时，我只有 1 个决定，请检查 b < c。如果为真，则 S={b,c}。否则，S={c,b}。
之前合并 b 和 c 返回的任何内容都与 S={a} 合并。
在S={a}和S={b,c}的合并中，我有几个决定。我首先检查是否 a < b。如果为真，并且由于 S={b,c} 已排序，则 S={a,b,c}。如果为假，我还有另一个决定要做。检查是否 a < c。如果为真，则 S={b,a,c}。否则，S={b,c,a}.
这让我陷入困境。如何将我的所有工作合并到一个决策树中？我可以毫无问题地为迭代算法创建决策树，但是由于该算法是递归的，所以我很困惑。
感谢任何帮助。谢谢。
您必须从递归的最深层开始遵循补丁。在这种情况下，树的顶部是 "if (b <= c)"。那么如果为真，正如你已经提到的，它是 "if (a <= b") S={a,b,c} else "if (a <= c") S = {b,a,c}" "else S = {b, c, a}"，那么"if (b <= c)" 为假时的模式类似。
我不确定这有什么意义。在 n=4 的情况下，您有 24 种可能的排列，对于 n = 5，有 120 种排列，相当大的树。
在我的作业中，我需要为任意输入 S={a,b,c} 创建 n=3 的决策树。
这是我的递归调用树。 S={a,b,c} 变成 S={a} 和 S={b,c} 和 S={b,c} 变成 S={b} 和 S={c}。在基本情况下，我有 S={a}、S={b} 和 S={c}。
当我将 S={b} 与 S={c} 合并时，我只有 1 个决定，请检查 b < c。如果为真，则 S={b,c}。否则，S={c,b}。
之前合并 b 和 c 返回的任何内容都与 S={a} 合并。
在S={a}和S={b,c}的合并中，我有几个决定。我首先检查是否 a < b。如果为真，并且由于 S={b,c} 已排序，则 S={a,b,c}。如果为假，我还有另一个决定要做。检查是否 a < c。如果为真，则 S={b,a,c}。否则，S={b,c,a}.
这让我陷入困境。如何将我的所有工作合并到一个决策树中？我可以毫无问题地为迭代算法创建决策树，但是由于该算法是递归的，所以我很困惑。
感谢任何帮助。谢谢。
您必须从递归的最深层开始遵循补丁。在这种情况下，树的顶部是 "if (b <= c)"。那么如果为真，正如你已经提到的，它是 "if (a <= b") S={a,b,c} else "if (a <= c") S = {b,a,c}" "else S = {b, c, a}"，那么"if (b <= c)" 为假时的模式类似。
我不确定这有什么意义。在 n=4 的情况下，您有 24 种可能的排列，对于 n = 5，有 120 种排列，相当大的树。