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

Author

zephyr

Description

There are two points , and data points in a 2-dimensional Euclidean plane. Assume that the distance between and , and the distances between and the data points are given. The distances between and the data points are not given, but a function defined below can be used to identify the sign of for .

Assume that for any .

(1) Show the pseudo-code of an algorithm to sort by ascending order of the distances from in worst computational time.

(2) Explain why the worst computational time of the algorithm shown in (1) is .

(3) Prove that if then .

(4) When are already sorted by ascending order of the distances from , show an algorithm to sort by ascending order of the distances from that calls function the minimum number of times, and evaluate that number of times.

Kai

(1) Pseudo-code to sort by ascending order of the distances from

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 in worst computational time.

(2) Explain the worst computational time of the algorithm shown in (1) is

The merge sort algorithm has a time complexity of , where is the number of elements to sort because it divides the array into two halves and recursively sorts them in a time complexity of in each step. In this case, , so the time complexity of the merge sort algorithm is .

(3) Prove that if then

Consider 2 triangles formed by points , , and , :

• with sides , , and

• with sides , , and

By the triangle inequality, we have:

Given that , we can write:

Therefore, .

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

Given that for any , we can find out that for any (), since . This implies that by the proof in (3).

Therefore, we can sort by combining two sorted arrays and , where and are sorted by and , respectively.

So we can use the following algorithm to merge two sorted arrays and :

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 is called

The function is called times in the worst case. This is because the function is called for each pair of points in the two sorted arrays of points each. The function is called times to compare the distances between the points in the two arrays.

Knowledge

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

难点解题思路

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

解题技巧和信息

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

重点词汇

• 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