跳到主要内容

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

Author​

adj-matrix

Description​

I.​

TODO

II.​

Consider the following algorithm , which overwrites an input array of distinct non-negative integers to sort its components in ascending order:

  1. for or , do nothing.
  2. for , do nothing if , and overwrite as , otherwise.
  3. for , select an element of by using a function as . Let be an array consisting of all the elements in being smaller than , and be an array consisting of all the elements in being greater than . Overwrite as . Then, recursively apply to the subarrays and in as and , respectively.

Answer the following questions.

(1) Fig. 8 exemplifies the operation of for an array when and the order of the elements in and inherits their order in . Draw the operation of for by following the diagram in Fig. 8.

(2) Suppose that an array contains each integer from 1 to 9, once each. Also, assume that and the order of the elements in and inherits their order in . Obtain the array that maximizes the number of recursive calls of and has the largest value evaluated as a 9-digit integer. Also obtain the array that minimizes the number of recursive calls of and has the largest value evaluated as a 9-digit integer. Note that the value of evaluated as a 9-digit integer is 123456789.

(3) Assume that . For an array with length , 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 in the C programming language. Describe the codes that should be in the blanks, [A], [B], and [C].

(5) Suppose that is a function that returns an element selected from uniformly and randomly. Answer the order of the average time complexity of as a function of . 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;
}

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. .

For , 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

Since is constant, therefore

i.e. , i.e. the time complexity is

(4)​

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

(5)​

Complexity:

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. . Since the partitioning operation at each level of recursion trees takes time in total, the total expected time complexity is .

The expected running time satisfies: i.e.

目录