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

标签：

• Tokyo-University
• Merge-Sort

Author

zephyr

Description

We wish to sort an array of integers, $a_1, a_2, \ldots, a_{2^t}$ ($n$ is a natural number) in ascending order. Assume that loading/storing an integer and comparing two integers take unit time.

(1) Let $n = 1$. Show an algorithm that sorts the array, $a_1, a_2$.

(2) Given two sorted arrays, $x_1, x_2, \ldots, x_p$ and $y_1, y_2, \ldots, y_q$, show an algorithm that merges the two arrays and calculates the sorted array $z_1, z_2, \ldots, z_{p+q}$ in $O(p + q)$ time.

(3) Let $T(2^n)$ be the running time for sorting an array, $a_1, a_2, \ldots, a_{2^n}$. We sort the first half of the array in $T(2^{n-1})$ time, and sort the second half similarly. Then we obtain the full sorted array by merging the first and second half of the arrays using the algorithm we used in (2). Derive the recurrence for $T(2^n)$ in terms of $T(2^{n-1})$ and $n$, and then derive an explicit formula for $T(2^n)$.

(4) Notice that in (2), the first half of the sorted array, $z_1, z_2, \ldots, z_{\lceil \frac{p+q}{2} \rceil}$, contains the first $t$ elements of $x_1, x_2, \ldots, x_p$ and the first $\lceil \frac{p+q}{2} \rceil - t$ elements of $y_1, y_2, \ldots, y_q$. Given two sorted arrays, $x_1, x_2, \ldots, x_p$ and $y_1, y_2, \ldots, y_q$, show an algorithm that finds $t$ in $O(\log(p + q))$ time. For simplicity, you may assume that $a_1, a_2, \ldots, a_{2^t}$ are distinct numbers.

(5) Assume that we have $O(2^n)$ CPU cores, and assume that we can ignore the synchronization cost between CPU cores. Show the running time complexity of a parallel merge sort algorithm that uses the technique in (4).

---

我们希望按升序排序一个整数数组 $a_1, a_2, \ldots, a_{2^t}$ ($n$ 是一个自然数)。假设加载/存储一个整数和比较两个整数所需的时间是单位时间。

(1) 令 $n = 1$。展示一个排序数组 $a_1, a_2$ 的算法。

(2) 给定两个已排序的数组 $x_1, x_2, \ldots, x_p$ 和 $y_1, y_2, \ldots, y_q$，展示一个算法，将这两个数组合并并计算排序后的数组 $z_1, z_2, \ldots, z_{p+q}$，时间复杂度为 $O(p + q)$。

(3) 设 $T(2^n)$ 为排序数组 $a_1, a_2, \ldots, a_{2^n}$ 的运行时间。我们在 $T(2^{n-1})$ 时间内对数组的前半部分进行排序，并以类似方式对后半部分进行排序。然后我们通过使用 (2) 中的算法合并数组的前半部分和后半部分来获得完全排序的数组。推导 $T(2^n)$ 的递推关系，并得出 $T(2^n)$ 的显式公式。

(4) 注意在 (2) 中，排序后的数组的前半部分 $z_1, z_2, \ldots, z_{\lceil \frac{p+q}{2} \rceil}$ 包含了 $x_1, x_2, \ldots, x_p$ 的前 $t$ 个元素和 $y_1, y_2, \ldots, y_q$ 的前 $\lceil \frac{p+q}{2} \rceil - t$ 个元素。给定两个已排序的数组 $x_1, x_2, \ldots, x_p$ 和 $y_1, y_2, \ldots, y_q$，展示一个在 $O(\log(p + q))$ 时间内找到 $t$ 的算法。为了简单起见，你可以假设 $a_1, a_2, \ldots, a_{2^t}$ 是不同的数字。

(5) 假设我们有 $O(2^n)$ 个 CPU 核，并假设可以忽略 CPU 核之间的同步成本。展示使用 (4) 中技术的并行归并排序算法的运行时间复杂度。

Kai

(1)

For $n=1$, the array has only two elements, $a_1$ and $a_2$. We can sort this array with a simple comparison and swap if needed.

Algorithm:

1. Compare $a_1$ and $a_2$.
2. If $a_1 > a_2$, swap them.

Pseudocode:

if a_1 > a_2 then
    swap(a_1, a_2)

(2)

Given two sorted arrays $\mathbf{x} = [x_1, x_2, \ldots, x_p]$ and $\mathbf{y} = [y_1, y_2, \ldots, y_q]$, we merge them into a single sorted array $\mathbf{z} = [z_1, z_2, \ldots, z_{p+q}]$.

Algorithm:

1. Initialize pointers $i$, $j$, and $k$ to $1$.
2. While both arrays have elements to be compared:
   • Compare $\mathbf{x}[i]$ and $\mathbf{y}[j]$.
   • Append the smaller element to $\mathbf{z}[k]$ and increment the corresponding pointer.
   • Increment $k$.
3. If one array is exhausted, append the remaining elements of the other array to $\mathbf{z}$.

Pseudocode:

i, j, k = 1, 1, 1
while i <= p and j <= q do
    if x_i < y_j then
        z_k = x_i
        i = i + 1
    else
        z_k = y_j
        j = j + 1
    k = k + 1

while i <= p do
    z_k = x_i
    i = i + 1
    k = k + 1

while j <= q do
    z_k = y_j
    j = j + 1
    k = k + 1

The time complexity of this algorithm is $O(p + q)$.

(3)

We sort the first and second halves of the array separately and then merge them. The recurrence relation is:

$$T(2^n) = 2T(2^{n-1}) + O(2^n)$$

The $O(2^n)$ term comes from the merging step.

To solve this recurrence, we can use the Master Theorem for divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$. Here, $a = 2$, $b = 2$, and $f(n) = O(n)$.

According to the Master Theorem:

• If $f(n) = O(n^{\log_b a})$, then $T(n) = O(n^{\log_b a} \log n)$.
• $\log_b a = \log_2 2 = 1$.

Thus, $f(n) = O(n)$ matches $O(n^{\log_b a})$. Therefore,

$$T(2^n) = O(2^n \log 2^n) = O(n 2^n)$$

(4)

We need to find the position $t$ such that the first $\lceil \frac{p+q}{2} \rceil$ elements of the merged array come from the first $t$ elements of $\mathbf{x}$ and the first $\lceil \frac{p+q}{2} \rceil - t$ elements of $\mathbf{y}$.

Algorithm:

1. Perform a binary search on $\mathbf{x}$ to find $t$.
2. Initialize low and high pointers: $low = 0$ and $high = p$.
3. While $low \leq high$:
   • Set $t = \frac{low + high}{2}$.
   • Set $s = \lceil \frac{p+q}{2} \rceil - t$.
   • Check the conditions to adjust the pointers:
     • If $\mathbf{x}[t-1] \leq \mathbf{y}[s]$ and $\mathbf{y}[s-1] \leq \mathbf{x}[t]$, then $t$ is found.
     • If $\mathbf{x}[t-1] > \mathbf{y}[s]$, adjust $high$.
     • Otherwise, adjust $low$.

Pseudocode:

low, high = 1, p+1
while low <= high do
    t = (low + high) / 2
    s = ceil((p + q) / 2) - t
    if x_t <= y_s+1 and y_s <= x_t+1 then
        return t
    else if x_t > y_s+1 then
        high = t - 1
    else
        low = t + 1

The time complexity of this algorithm is $O(\log(p + q))$ due to the binary search.

(5)

Assuming $O(2^n)$ CPU cores and ignoring synchronization costs, we can sort each half of the array in parallel.

For each level of recursion, the work is divided equally among available cores. Therefore, the time complexity at each level is determined by the depth of the recursion tree.

The depth of the recursion tree is $n$, and each merge operation at each level takes $O(2^n)$ divided by the number of available cores.

Overall Time Complexity:

$$O\left(\frac{2^n \log 2^n}{2^n}\right) = O(\log 2^n) = O(n)$$

Thus, the parallel merge sort algorithm with $O(2^n)$ CPU cores has a time complexity of $O(n)$.

Knowledge

归并排序 二分查找 并行计算 排序算法

难点思路

在第四部分，找到合适的 $t$ 使得合并的前半部分数组满足特定条件是一个难点。利用二分查找可以有效减少时间复杂度。

解题技巧和信息

• 归并排序是一种分治算法，其时间复杂度为 $O(n \log n)$。
• 合并两个已排序数组的时间复杂度为 $O(p + q)$。
• 利用二分查找可以在 $O(\log n)$ 时间内找到特定位置。
• 并行计算可以显著加速大规模数据的排序。

重点词汇

• merge 合并
• binary search 二分查找
• parallel computation 并行计算

参考资料

1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chapter 2: Getting Started.
2. The Art of Computer Programming, Donald E. Knuth, Volume 3: Sorting and Searching, Section 5.2.4: Merge Sort.