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

标签：

• Tokyo-University
• Merge-Sort

Author

zephyr, 祭音Myyura

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) 中技术的并行归并排序算法的运行时间复杂度。

题目描述

要把整数数组升序排列，并假设一次整数读取、写入或两整数比较均耗费单位时间。Description 首句把数组长度写作 $2^t$、同时称 $n$ 为自然数；后续第 (3) 至 (5) 问统一使用长度 $2^n$。以下保留各小问实际给出的记号：

1. 当 $n=1$ 时，给出排序 $a_1,a_2$ 的算法。

2. 给定两个已升序排列的数组 $x_1,\ldots,x_p$ 与 $y_1,\ldots,y_q$，给出在 $O(p+q)$ 时间内合并为 $z_1,\ldots,z_{p+q}$ 的算法。

3. 令 $T(2^n)$ 为排序 $a_1,\ldots,a_{2^n}$ 的时间。分别以 $T(2^{n-1})$ 排序前、后半段，再用第 2 问算法合并；写出 $T(2^n)$ 关于 $T(2^{n-1})$ 与 $n$ 的递推式，并求显式公式。

4. 记

   $$q'=\left\lceil\frac{p+q}{2}\right\rceil.$$

   合并结果的前半段 $z_1,\ldots,z_{q'}$ 恰由 $x$ 的前 $t$ 项和 $y$ 的前 $q'-t$ 项组成。给出在 $O(\log(p+q))$ 时间内找到 $t$ 的算法；为简化，可假设原长度为 $2^t$ 的数组中各数互异。

5. 假设有 $O(2^n)$ 个 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}) + \Theta(2^n)$$

The $\Theta(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) = \Theta(n)$.

According to the Master Theorem:

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

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

$$T(2^n) = \Theta(2^n \log 2^n) = \Theta(n 2^n).$$

More explicitly, if merging $2^n$ elements costs $c2^n$ and $T(2)=T_1$, then $T(2^n)=2^{n-1}T_1+c(n-1)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. Put $r=\lceil(p+q)/2\rceil$ and initialize $low=\max(0,r-q)$ and $high=\min(p,r)$.
3. While $low \leq high$:
   • Set $t = \lfloor(low + high)/2\rfloor$.
   • Set $s = r-t$.
   • Check the conditions to adjust the pointers:
     • If $x_t\le y_{s+1}$ and $y_s\le x_{t+1}$, then $t$ is found.
     • If $x_t>y_{s+1}$, adjust $high$.
     • Otherwise, adjust $low$.

Use sentinels $x_0=y_0=-\infty$ and $x_{p+1}=y_{q+1}=+\infty$.

Pseudocode:

r = ceil((p + q) / 2)
low, high = max(0, r - q), min(p, r)
while low <= high do
    t = floor((low + high) / 2)
    s = r - 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, sort the two halves in parallel. To merge two sorted arrays of total length $2^k$, use (4) to split the output in half, and recursively merge the two pairs of subarrays in parallel.

Let $M(k)$ be the parallel merge time. The binary search at one merge level costs $O(k)$, while the two recursive merges run simultaneously. Hence:

$$M(k)=M(k-1)+O(k)=O(k^2).$$

If $P(k)$ is the parallel sorting time, the two recursive sorts also run simultaneously, followed by the merge:

$$P(k)=P(k-1)+M(k)=O(k^3).$$

Thus, this parallel merge sort runs in $O(n^3)=O(\log^3(2^n))$ time. At most $O(2^n)$ merge subproblems exist at once, so the assumed number of cores is sufficient.

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.