CBMS-2023-10

题目来源：Problem 10 日期：2024-07-11 题目主题：CS-算法-排序

具体题目

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 $ϵ$ 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\le i<j\le 2^n$.

$$f(P_i,P_j)=\mathrm{sgn}(b_i-b_j)=\{\begin{array}{ll}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{array}$$

Assume that $|a_i-a_j|>ϵ$ for any $a_i,a_j$ $(1\le i\le j\le 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(n{2}^n)$ worst computational time.
2. Explain why the worst computational time of the algorithm shown in (1) is $O(n{2}^n)$.
3. Prove that if $a_i-a_j>2ϵ$ 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.

正确解答

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(n{2}^n)$ worst computational time.

2. Explain the worst computational time of the algorithm shown in (1) is $O(n{2}^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(n{2}^n)$.

3. Prove that if $a_i-a_j>2ϵ$ then $b_i>b_j$

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

• $△AB{P}_i$ with sides $a_i$, $b_i$, and $ϵ$

• $△AB{P}_j$ with sides $a_j$, $b_j$, and $ϵ$

By the triangle inequality, we have:

$$b_i+ϵ\ge a_i\text{and}{a}_i+ϵ\ge b_i$$

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

$$b_i+ϵ\ge a_i>a_j+2ϵ\ge b_j+ϵ$$

Therefore, $b_i>b_j$.

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

Given that $|a_i-a_j|>ϵ$ for any $a_i,a_j$, we can find out that for any $i$ ($1\le i\le 2^n-2$), $a_{i+2}-a_i>2ϵ$ since $|a_{i+2}-a_i|=|a_{i+2}-a_{i+1}+a_{i+1}-a_i|\ge |a_{i+2}-a_{i+1}|+|a_{i+1}-a_i|>2ϵ$. 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.

知识点

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

难点解题思路

• 通过归并排序方法来排序点集 $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