東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題9
Author
Description
We wish to sort an array of integers,
(1) Let
(2) Given two sorted arrays,
(3) Let
(4) Notice that in (2), the first half of the sorted array,
(5) Assume that we have
我们希望按升序排序一个整数数组
(1) 令
(2) 给定两个已排序的数组
(3) 设
(4) 注意在 (2) 中,排序后的数组的前半部分
(5) 假设我们有
Kai
(1)
For
Algorithm:
- Compare
and . - If
, swap them.
Pseudocode:
if a_1 > a_2 then
swap(a_1, a_2)
(2)
Given two sorted arrays
Algorithm:
- Initialize pointers
, , and to . - While both arrays have elements to be compared:
- Compare
and . - Append the smaller element to
and increment the corresponding pointer. - Increment
.
- Compare
- If one array is exhausted, append the remaining elements of the other array to
.
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
(3)
We sort the first and second halves of the array separately and then merge them. The recurrence relation is:
The
To solve this recurrence, we can use the Master Theorem for divide-and-conquer recurrences of the form
According to the Master Theorem:
- If
, then . .
Thus,
(4)
We need to find the position
Algorithm:
- Perform a binary search on
to find . - Initialize low and high pointers:
and . - While
: - Set
. - Set
. - Check the conditions to adjust the pointers:
- If
and , then is found. - If
, adjust . - Otherwise, adjust
.
- If
- Set
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
(5)
Assuming
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
Overall Time Complexity:
Thus, the parallel merge sort algorithm with
Knowledge
归并排序 二分查找 并行计算 排序算法
难点思路
在第四部分,找到合适的
解题技巧和信息
- 归并排序是一种分治算法,其时间复杂度为
。 - 合并两个已排序数组的时间复杂度为
。 - 利用二分查找可以在
时间内找到特定位置。 - 并行计算可以显著加速大规模数据的排序。
重点词汇
- merge 合并
- binary search 二分查找
- parallel computation 并行计算
参考资料
- Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chapter 2: Getting Started.
- The Art of Computer Programming, Donald E. Knuth, Volume 3: Sorting and Searching, Section 5.2.4: Merge Sort.