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

标签：

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

Author

zephyr

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 \leq 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$。题面另给距离分离条件

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

原文把其下标范围写为 $1\le i\le j\le2^n$；当 $i=j$ 时该不等式不可能成立，现有 Description 与 Kai 均未给出能消除这一边界矛盾的额外条件。

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$ 的调用次数最少，并精确评价调用次数。

考点

• 归并排序与复杂度：对 $2^n$ 个已知键值使用稳定的分治排序，并由层数 $n$、每层工作量 $2^n$ 得到最坏界。
• 度量距离次序迁移：利用三角不等式从 $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_by_distances_from_A(points, distances_from_A):
    if len(points) <= 1:
        return points
    mid = len(points) // 2
    left_half = merge_sort_by_distances_from_A(points[:mid], distances_from_A[:mid])
    right_half = merge_sort_by_distances_from_A(points[mid:], distances_from_A[mid:])
    return merge(left_half, right_half, distances_from_A)

def merge(left, right, distances_from_A):
    sorted_points = []
    while left and right:
        if distances_from_A[left[0]] < distances_from_A[right[0]]:
            sorted_points.append(left.pop(0))
        else:
            sorted_points.append(right.pop(0))
    sorted_points.extend(left)
    sorted_points.extend(right)
    return sorted_points

points = [P_1, P_2, ..., P_{2^n}]
distances_from_A = [a_1, a_2, ..., a_{2^n}]
sorted_points = merge_sort_by_distances_from_A(points, distances_from_A)

P.S.: Quicksort can also be used to sort the points by distances from $A$ in $O(n2^n)$ worst computational time.

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

The merge sort algorithm has a time complexity of $O(k \log k)$, where $k$ is the number of elements to sort because it divides the array into two halves and recursively sorts them in a time complexity of $O(k)$ in each step. In this case, $k = 2^n$, so the time complexity of the merge sort algorithm is $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 $|a_i - a_j| > \epsilon$ for any $a_i, a_j$, we can find out that for any $i$ ($1 \leq i \leq 2^n-2$), $a_{i+2} - a_i > 2\epsilon$ since $|a_{i+2} - a_i| = |a_{i+2} - a_{i+1} + a_{i+1} - a_i| \geq |a_{i+2} - a_{i+1}| + |a_{i+1} - a_i| > 2\epsilon$. This implies that $b_{i+2} > b_i$ by the proof in (3).

Therefore, we can sort $B_1, \cdots, B_{2^n}$ by combining two sorted arrays $B_{2i}$ and $B_{2i+1}$, where $B_{2i+1}$ and $B_{2i}$ are sorted by $a_{2i+1}$ and $a_{2i}$, respectively.

So we can use the following algorithm to merge two sorted arrays $B_{2i}$ and $B_{2i+1}$:

def sort_by_distances_from_B(points, distances_from_A, distances_from_B):
    # 2^n points sorted by distances from A
    sorted_points = []
    i, j = 0, 0 # Pointers for the two sorted arrays

    # Merge the two sorted arrays of n/2 points each
    while i < len(points) and j < len(points):
        if f(points[i], points[j]) == 1: # b_i > b_j
            sorted_points.append(points[i])
            i += 1
        else:
            sorted_points.append(points[j])
            j += 1

    return sorted_points

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

The function $f$ is called $2^{n-1}$ times in the worst case. This is because the function $f$ is called for each pair of points in the two sorted arrays of $2^{n-1}$ points each. The function $f$ is called $2^{n-1}$ times to compare the distances between the points in the two arrays.

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