東京大学 工学系研究科 電気系工学専攻 2024年8月実施 問題4 情報工学II

标签：

• Tokyo-University
• Quick-Sort

Author

adj-matrix

Description

I.

TODO

II.

Consider the following algorithm $f(X)$, which overwrites an input array $X = (x_1, x_2, \cdots, x_n)$ of $n$ distinct non-negative integers to sort its components in ascending order:

1. for $n = 0$ or $n = 1$, do nothing.
2. for $n = 2$, do nothing if $x_1 < x_2$, and overwrite $X$ as $X = (x_2, x_1)$, otherwise.
3. for $n > 2$, select an element $p$ of $X$ by using a function $h(X)$ as $p = h(X)$. Let $X_1$ be an array consisting of all the elements in $X$ being smaller than $p$, and $X_2$ be an array consisting of all the elements in $X$ being greater than $p$. Overwrite $X$ as $X = (X_1, p, X_2)$. Then, recursively apply $f$ to the subarrays $X_1$ and $X_2$ in $X$ as $f(X_1)$ and $f(X_2)$, respectively.

Answer the following questions.

(1) Fig. 8 exemplifies the operation of $f$ for an array $X = (6,9,3,5,1,7)$ when $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Draw the operation of $f$ for $X = (6,8,4,5,2,3,1,9,7)$ by following the diagram in Fig. 8.

(2) Suppose that an array $X$ contains each integer from 1 to 9, once each. Also, assume that $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Obtain the array $X_{\max}$ that maximizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Also obtain the array $X_{\min}$ that minimizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Note that the value of $X = (1,2,3,4,5,6,7,8,9)$ evaluated as a 9-digit integer is 123456789.

(3) Assume that $h(X) = x_1$. For an array $X$ with length $n$, obtain the order of worst-case time complexity by supplementing the intermediate steps of its derivation. In the derivation, evaluate the order of the time complexity in terms of comparisons, while ignoring the complexity of the other operations.

(4) Program 1 is an implementation of the algorithm $f(X)$ in the C programming language. Describe the codes that should be in the blanks, [A], [B], and [C].

(5) Suppose that $h(X)$ is a function that returns an element $p$ selected from $X$ uniformly and randomly. Answer the order of the average time complexity of $f(X)$ as a function of $n$. In addition, describe its reason in detail.

Fig. 8

        (6,9,3,5,1,7)
              |
   (3,5,1) -- 6 - (9,7)
      |       |     |
(1) - 3 - (5) |   (7,9)
 |____|____|  |     |
      |       |     |
   (1,3,5) -- 6 - (7,9)
              |
        (1,3,5,6,7,9)

/* Program1 */
void swap(int X[], int i, int j){
    int tmp = X[i]; X[i] = X[j]; X[j] = tmp;
}
int partition (int X[], int left, int right) {
    int pivot = X[left];
    int i = right;
    for (int j = right; j >= left+1; j--) {
        if (X[j] >= pivot) {
            [A]
            i--;
        }
    }
    [B]
    return i;
}
void f(int X[], int left, int right) {
    if (left < right) {
        int pivotpos = partition(X, left, right);
        [C]
    }
}
int main (void) {
    int X[10] = {9, 6, 1, 7, 2, 3, 4, 5, 0, 8};
    f(X, 0, sizeof(X) / sizeof(X[0]) - 1);
    return 0;
}

题目描述

原 Description 的第一部分只有 TODO，Kai 的对应部分也只有 TODO，因此本地内容无法确认第一部分的具体题干。

第二部分定义递归排序算法 $f(X)$。输入是由 $n$ 个互不相同的非负整数组成的数组 $X=(x_1,\ldots,x_n)$：$n\le1$ 时不操作；$n=2$ 时按升序交换；$n>2$ 时由 $p=h(X)$ 选枢轴，把小于 $p$ 的元素组成 $X_1$、大于 $p$ 的元素组成 $X_2$，将数组改写为 $(X_1,p,X_2)$，再分别递归排序 $X_1,X_2$。

1. 当 $h(X)=x_1$，且划分后各元素保持原相对次序时，仿照图 8，完整画出 $X=(6,8,4,5,2,3,1,9,7)$ 的递归划分与最终排序过程。
2. $X$ 恰含整数 $1$ 至 $9$ 各一次，仍取首元素为枢轴并保持相对次序。求使递归调用次数最多、且作为九位整数时数值最大的数组 $X_{\max}$；再求使递归调用次数最少且九位整数值最大的数组 $X_{\min}$。
3. 当 $h(X)=x_1$ 时，以元素比较次数为准，补出递推推导的中间步骤并求长度为 $n$ 的数组在最坏情况下的时间复杂度阶。
4. 补全给定 C 程序中 partition 的 [A]、[B] 和递归函数 f 的 [C]，使程序实现上述划分与排序。
5. 若 $h(X)$ 从 $X$ 中均匀随机选取枢轴，给出 $f(X)$ 的平均时间复杂度阶，并详细说明随机划分、递归树高度和每层工作量如何导出该结论。

Kai

I.

TODO

II.

(1)

             (6,8,4,5,2,3,1,9,7)
                      |
       (4,5,2,3,1) -- 6 -- (8,9,7)
              |       |       |
  (2,3,1) --- 4 - (5) | (7) - 8 - (9)
      |       |    |  |  |____|____|
(1) - 2 - (3) |    |  |       |
 |____|____|  |    |  |    (7,8,9)
      |       |    |  |       |
   (1,2,3)    |    |  |       |
      |_______|____|  |       |
              |       |       |
         (1,2,3,4,5)  |       |
              |_______|_______|
                      |
             (1,2,3,4,5,6,7,8,9)

(2)

The worst case is when the partition is as unbalanced as possible. Since we want the digits at the start of the array to be as large as possible. In addition, each integer from 1 to 9 is one each. Therefore, the worst case is 987654321, i.e. $X_{\max}$.

For $X_{\min}$, we want this case: (from bottom to top)

       (1,2,3,4,5,6,7,8,9)
         _______|_________
        |       |         |
    (1,2,3,4)   5     (6,7,8,9)
   _____|____   |    _____|____
  |     |    |  |   |     |    |
(1,2) - 3 - (4) | (6,7) - 8 - (9)
        |       |         |
    (3,4,2,1) - 5 --- (8,9,7,6)
                |
       (5,8,9,7,6,3,4,2,1)

Therefore, the best and largest case is 589763421.

(Note to readers: The C code provided in the question is unstable; it will swap the Pivot to the middle and swap the elements that were originally at the end to the beginning)

(3)

In the worst case, the time complexity $T(n) = T(n-1) + T(0) + O(n)$

Since $T(0)$ is constant, therefore $T(n) = T(n-1) + cn = cn + c(n-1) + c(n-2) + \dots + c(1) \approx c \frac{n(n+1)}{2}$

i.e. $T(n) = O(n^2)$, i.e. the time complexity is $O(n^2)$

(4)

• A: swap(X, i, j);
• B: swap(X, left, i);
• C: f(X, left, pivotpos-1); f(X, pivotpos+1, right)

(5)

Complexity: $O(n \log n)$

Reason:

On average, the randomly chosen pivots splits the array into two subarrays of roughly proportional sizes. Because balanced or near-balanced splits occur with constant probability, the expected height of the recursion tree becomes logarithmic, i.e. $O(\log n)$. Since the partitioning operation at each level of recursion trees takes $O(n)$ time in total, the total expected time complexity is $O(n) \cdot O(\log n) = O(n \log n)$.

The expected running time $T(n)$ satisfies: $T(n) = O(n) + \frac{1}{n} \sum_{i=0}^{n-1} (T(i) + T(n-1-i))$ i.e. $T(n) = O(n \log n)$