東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題7

标签：

• Tokyo-University
• Comparison-Sorting-Decision-Tree-Lower-Bound
• Information-Theoretic-Lower-Bound

Author

zephyr, 祭音Myyura

Description

To determine the order of $n \ (\geq 3)$ elements (different natural numbers) $a_1, \ldots, a_n$, we generate a binary tree starting from the root node by repeating the following step:

• At each node, if the order of all elements has been determined, let the node be a leaf and label it with the order of all elements. Otherwise, select a pair of elements $a_i, a_j \ (i < j)$ whose order has not yet been determined, and compare them. If $a_i < a_j$, go to the left child node; otherwise, go to the right child node.

We call such a binary tree a decision tree. A decision tree shows how a sorting algorithm compares elements.

Answer the following questions:

(1) When $n$ is fixed, among all paths from the root to leaves in all decision trees, describe a shortest path and a longest path.

(2) Prove that in any decision tree, any order of all elements appears in one leaf but does not appear in different leaves.

(3) Let $h$ denote the height of a decision tree. Prove $c n \log n \leq h$ for a constant $c$.

---

为了确定 $n \ (\geq 3)$ 个元素（不同的自然数）$a_1, \ldots, a_n$ 的顺序，我们通过重复以下步骤生成一棵二叉树：

• 在每个节点，如果所有元素的顺序已经确定，则让该节点成为叶子并标记为所有元素的顺序。否则，选择一对顺序尚未确定的元素 $a_i, a_j \ (i < j)$，并比较它们。如果 $a_i < a_j$，则转到左子节点；否则，转到右子节点。

我们将这种二叉树称为决策树。决策树显示了排序算法如何比较元素。

回答以下问题：

(1) 当 $n$ 固定时，在所有决策树中从根到叶的所有路径中，描述最短路径和最长路径。

(2) 证明在任何决策树中，所有元素的任何顺序出现在一个叶子中，但不会出现在不同的叶子中。

(3) 令 $h$ 表示决策树的高度。证明 $c n \log n \leq h$ 对于某个常数 $c$。

题目描述

要确定 $n\ge3$ 个互异自然数 $a_1,\ldots,a_n$ 的全序，从根开始反复构造二叉树：若当前已有比较结果足以确定全部元素顺序，则把当前节点作为叶，并以该全序标记；否则选择一对尚未确定相对次序的 $a_i,a_j$（$i<j$）比较，若 $a_i<a_j$ 则进入左孩子，否则进入右孩子。这样的树称为排序的比较决策树。

1. 固定 $n$，在所有决策树的所有根到叶路径中，描述可能的最短路径与最长路径。

2. 证明在任意决策树中，每一种元素全序必出现在某一个叶节点，且不可能同时标记不同叶节点。

3. 令决策树高度为 $h$，证明存在常数 $c>0$ 使

   $$cn\log n\le h.$$

Kai

(1)

To sort $n$ elements, we need to compare some pairs of elements. Each comparison gives us one bit of information. The shortest path from the root to a leaf in a decision tree corresponds to the minimum number of comparisons needed to determine the order of all elements. The longest path corresponds to the maximum number of comparisons needed.

Shortest Path

A path of length $n-1$ is obtained by comparing consecutive elements and following the outcomes:

For $n$ elements $a_1, a_2, \ldots, a_n$, the comparisons would look like:

• $a_1 < a_2$
• $a_2 < a_3$
• $a_3 < a_4$
• $\ldots$
• $a_{n-1} < a_n$

These comparisons determine $a_1<a_2<\cdots<a_n$. Conversely, the graph whose edges are the compared pairs must be connected; otherwise elements in different components have no determined relative order. Hence every path has at least $n-1$ comparisons, so the shortest length is $n-1$.

Longest Path

No unordered pair can be compared twice, so a path has length at most $\binom n2$. This bound is attained by comparing the pairs in the following order and following the outcomes $a_1>a_2>\cdots>a_n$:

• Compare $a_1$ with $a_2$
  • Compare $a_1$ with $a_3$
    • Compare $a_1$ with $a_4$
    • $\ldots$
    • Compare $a_1$ with $a_n$
• Compare $a_2$ with $a_3$
  • Compare $a_2$ with $a_4$
  • $\ldots$
  • Compare $a_2$ with $a_n$
• $\ldots$
• Compare $a_{n-1}$ with $a_n$

When $(a_i,a_j)$ is compared in this order, its relation has not yet been implied transitively. Thus all $\binom n2=n(n-1)/2$ comparisons are permitted, and this is the longest path.

(2)

Existence

In any decision tree used for sorting $n$ elements, each leaf node represents a complete sequence of comparisons that uniquely determines the order of the elements. We need to show that any possible permutation of the $n$ elements appears in at least one leaf node.

Leaf Node Representation: Each leaf node corresponds to a unique permutation of the $n$ elements. As we build the tree from the root node, each comparison between two elements $a_i$ and $a_j$ (where $i < j$) directs us to a new child node, either left or right, based on the result of the comparison in the permutation of the elements, until we reach the leaf node.

Thus, each possible permutation of the elements must be represented by at least one path from the root to a leaf. This ensures that any order of all elements appears in one leaf node, satisfying the existence condition.

Uniqueness

Now, we need to prove that any given order of all $n$ elements appears in exactly one leaf node and does not appear in multiple leaf nodes.

1. Unique Comparison Paths: Each leaf node in a decision tree is reached by a unique sequence of comparisons. This sequence determines a specific permutation of the elements. If two different paths lead to the same permutation, then at least one comparison in the paths, which is located in the common ancestor of the two paths, would have to result in a contradiction.
2. Deterministic Nature of Comparisons: If two paths diverge, at their last common node the same pair is compared and the two branches require opposite outcomes. No single total order can satisfy both paths.
3. Conclusion: Therefore, any given order of all elements appears in exactly one leaf node and does not appear in different leaf nodes. This ensures the uniqueness condition.

(3)

To prove that $c n \log n \leq h$ for a constant $c$, we consider the following:

1. Information-Theoretic Argument: The height of a decision tree represents the maximum number of comparisons needed in the worst case. For $n$ elements, there are $n!$ possible permutations (orders). Each comparison splits the set of possible permutations, providing one bit of information.
2. Lower Bound on Comparisons: The number of comparisons needed to distinguish between $n!$ permutations is at least $\log_2(n!)$. For $n\ge4$, the largest $\lceil n/2\rceil$ factors in $n!$ are at least $n/2$, so:

$$\log_2(n!)\ge \frac n2\log_2\frac n2 \ge \frac n4\log_2 n.$$

1. Height Relation: The height $h$ of the decision tree must be at least $\log_2(n!)$. Therefore:

$$h \geq c n \log n$$

for a positive constant $c$ (with a constant adjustment for $n<4$).

Hence, we have shown that the height of the decision tree $h$ satisfies the inequality $c n \log n \leq h$.

Knowledge

决策树 排序算法 复杂度分析 信息论

重点词汇

• Decision Tree 决策树
• Comparison 比较
• Permutation 排列
• Information-Theoretic 信息论的
• Stirling's Approximation 斯特林近似

参考资料

1. "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, Chapter on Sorting and Order Statistics.
2. "The Art of Computer Programming" by Donald Knuth, Volume 3: Sorting and Searching.