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

标签：

• Tokyo-University
• Merge-Sort
• Metric-Order-Transfer-with-Minimum-Comparisons
• Algorithm-Complexity

Author

zephyr, 祭音Myyura

Description

There are two points $A$, $B$ and $2^n$ data points $P_1, \cdots, P_{2^n}$ in a 2-dimensional Euclidean plane. Assume that the distance $\epsilon$ between $A$ and $B$, and the distances $a_1, \cdots, a_{2^n}$ between $A$ and the data points are given. The distances $b_1, \cdots, b_{2^n}$ between $B$ and the data points are not given, but a function $f(P_i, P_j)$ defined below can be used to identify the sign of $b_i - b_j$ for $1 \leq i < j \leq 2^n$.

$$f(P_i, P_j) = \mathrm{sgn}(b_i - b_j) = \begin{cases} 1 & \text{if } b_i - b_j > 0 \\ 0 & \text{if } b_i - b_j = 0 \\ -1 & \text{if } b_i - b_j < 0 \end{cases}$$

Assume that $|a_i - a_j| > \epsilon$ for any $a_i, a_j$ $(1 \leq i < j \leq 2^n)$.

(1) Show the pseudo-code of an algorithm to sort $P_1, \cdots, P_{2^n}$ by ascending order of the distances from $A$ in $O(n2^n)$ worst computational time.

(2) Explain why the worst computational time of the algorithm shown in (1) is $O(n2^n)$.

(3) Prove that if $a_i - a_j > 2\epsilon$ then $b_i > b_j$.

(4) When $P_1, \cdots, P_{2^n}$ are already sorted by ascending order of the distances from $A$, show an algorithm to sort by ascending order of the distances from $B$ that calls function $f$ the minimum number of times, and evaluate that number of times.

题目描述

二维欧氏平面内有两点 $A,B$ 及 $2^n$ 个数据点 $P_1,\ldots,P_{2^n}$。已知 $A,B$ 间距离 $\epsilon$，以及 $A$ 到各数据点的距离 $a_1,\ldots,a_{2^n}$；未知 $B$ 到各点的距离 $b_1,\ldots,b_{2^n}$，但可调用

$$f(P_i,P_j)=\operatorname{sgn}(b_i-b_j)= \begin{cases} 1,&b_i-b_j>0,\\ 0,&b_i-b_j=0,\\ -1,&b_i-b_j<0 \end{cases}$$

来比较任意 $1\le i<j\le2^n$ 的两项 $b_i,b_j$。并假设对任意 $1\le i<j\le2^n$，距离满足

$$|a_i-a_j|>\epsilon.$$

1. 给出最坏 $O(n2^n)$ 时间内按 $a_i$ 升序排列 $P_1,\ldots,P_{2^n}$ 的伪代码。
2. 说明第 1 问算法为何具有该最坏时间复杂度。
3. 证明若 $a_i-a_j>2\epsilon$，则 $b_i>b_j$。
4. 已知各点已按到 $A$ 的距离升序排列，设计按到 $B$ 的距离升序排列它们的算法，使对比较函数 $f$ 的调用次数最少，并精确评价调用次数。

Kai

(1) Pseudo-code to sort $P_1, \cdots, P_{2^n}$ by ascending order of the distances from $A$

def merge_sort(items):                  # each item is (a_i, P_i)
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i][0] <= right[j][0]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

items = [(a_1, P_1), (a_2, P_2), ..., (a_{2^n}, P_{2^n})]
sorted_points = [point for _, point in merge_sort(items)]

P.S.: Heapsort can also achieve the same worst-case bound.

(2) Explain the worst computational time of the algorithm shown in (1) is $O(n2^n)$

The merge sort algorithm has time complexity $O(k\log k)$: merging costs $O(k)$ per recursion level, and there are $O(\log k)$ levels. Here $k=2^n$, so the complexity is $O(2^n\log 2^n)=O(n2^n)$.

(3) Prove that if $a_i - a_j > 2\epsilon$ then $b_i > b_j$

Consider 2 triangles formed by points $A$, $B$, and $P_i$, $P_j$:

• $\triangle ABP_i$ with sides $a_i$, $b_i$, and $\epsilon$

• $\triangle ABP_j$ with sides $a_j$, $b_j$, and $\epsilon$

By the triangle inequality, we have:

$$b_i + \epsilon \geq a_i \quad \text{and} \quad a_i + \epsilon \geq b_i$$

Given that $a_i - a_j > 2\epsilon$, we can write:

$$b_i + \epsilon \geq a_i > a_j + 2\epsilon \geq b_j + \epsilon$$

Therefore, $b_i > b_j$.

(4) Algorithm to sort by ascending order of the distances from $B$

Given that the points are sorted by $a_i$, for any $i$ ($1 \leq i \leq 2^n-2$),

$$a_{i+2}-a_i=(a_{i+2}-a_{i+1})+(a_{i+1}-a_i)>2\epsilon.$$

Thus $b_{i+2}>b_i$ by (3).

Therefore, the odd-indexed list $L=(P_1,P_3,\ldots,P_{2^n-1})$ and the even-indexed list $R=(P_2,P_4,\ldots,P_{2^n})$ are both already sorted by distance from $B$. Merge them as follows; compare_B uses one call to $f$ (reversing its sign when the arguments' original indices are reversed).

def merge_by_B(L, R):
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        if compare_B(L[i], R[j]) <= 0:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    result.extend(L[i:])
    result.extend(R[j:])
    return result

Evaluation of the number of times the function $f$ is called

Merging two lists with a total of $2^n$ elements uses at most

$$2^n-1$$

calls to $f$. This is optimal in the worst case: if the two lists alternate in the final order, each of the $2^n-1$ adjacent cross-list pairs must be compared; otherwise that pair could be interchanged without violating either list's known internal order.

Knowledge

排序算法 算法 复杂度分析 几何 三角不等式

难点解题思路

• 通过归并排序方法来排序点集 $P_1, \cdots, P_{2^n}$，利用三角不等式证明点与点之间距离的关系，提供了新的思路来求解几何问题。
• 利用归并排序和冒泡排序的结合，优化了排序过程中函数调用次数。

解题技巧和信息

• 对于复杂度分析，归并排序和冒泡排序是常见的有效方法。
• 使用几何和三角不等式的知识可以帮助解决关于点距离的问题。
• 在已知一个点集的部分顺序信息时，可以利用该信息减少计算量，优化算法。

重点词汇

• Sort 排序
• Merge 归并
• Triangle inequality 三角不等式
• Euclidean distance 欧几里得距离
• Computational complexity 计算复杂度

参考资料

1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein - Chapter on Sorting and Order Statistics
2. "Algorithms" by Robert Sedgewick and Kevin Wayne - Chapter on Sorting