大阪大学情報科学研究科情報工学 2023年8月実施アルゴリズムとプログラミング

标签：

Author

Description

ANSI-C 準拠である C 言語のプログラム 1, 2 は、データを読み込んで、要素を昇順に整列して出力する。入力するデータは、1 行目に整列する要素の個数 $n (n \ge 1)$ が、また 2 行目から $n+1$ 行目までに整列する要素として整数が各行に並べられた構造を持つ。データは、ファイル data.txt に記述されている。以下の各問に答えよ。

(1) 図 1 に示すプログラム 1 に関して、以下の各小問に答えよ。

(1-1) 図 2 の data.txt からデータを読み込んでプログラム 1 を実行した場合に、プログラム 1 の 20 行目が 3 回目に実行された直後の array[0], array[1], array[2], array[3], array[4] の値をそれぞれ示せ。
(1-2) 図 2 data.txt の 2 ~ 6 行目を並べ替え、プログラム 1 の 18 行目の実行回数が最大となる data.txt を示せ。
(1-3) 整列する要素の個数を $n$ とするとき、プログラム 1 の最悪時間計算量のオーダー表記として最も適しているものを下記選択肢から一つ選び、簡潔に理由も示せ。

$O(1)$ $O(\log n)$ $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n^2 \log n)$ $O(n^3)$

(2) プログラム 1 を部分的に改変しプログラム 2 を作成したい。以下の各小問に答えよ。ただし、data.txt は図 2 に限らないものとする。

(2-1) 探索を高速化させるため、プログラム 1 の 5~15 行目のみを図 3 の通り変更したプログラム 2 を作成する。空欄 [ (A) ] ~ [ (C) ] を適切な式で埋めて、プログラム 2 を完成させよ。
(2-2) 整列する要素の個数を $n$ とする。完成したプログラム 2 の最悪時間計算量のオーダー表記として最も適しているものを下記選択肢から一つ選び、簡潔に理由も示せ。

$O(1)$ $O(\log n)$ $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n^2 \log n)$ $O(n^3)$

(2-3) 完成したプログラム 2 の実行を開始してから終了するまでの間に、図 3 の 10 行目が実行される回数を $c$ とする。 $c$ は整列する要素の個数 $n$ と並び順に依存する。整列する要素がすべて異なるとき、 $c$ が最小となる要素の並び順が満たす要件を一つ示せ。
(2-4) (2-3) において、 $c$ の最小値を $n$ の式で示せ。導出過程も示すこと。

#include <stdio.h>
#include <stdlib.h>

void sort (int array[], int n) {
    int i, j, key, target;

    for (i = 1; i < n; i++) {
        key = array[i];

        for (j = 0; j < i; j++) {
            if (array[j] > key) {
                break;
            }
        }
        target = j;

        for (j = i - 1; j >= target; j--) {
            array[j + 1] = array[j];
        }
        array[target] = key;
    }
}

int main (void) {
    int N, i;
    FILE *fp;
    int *data;

    fp = fopen("data.txt", "r");
    fscanf(fp, "%d", &N);
    data = (int*) malloc(sizeof(int) * N);
    for (i = 0; i < N; i++) {
        fscanf(fp, "%d", &data[i]);
    }
    fclose(fp);

    sort(data, N);

    for (i = 0; i < N; i++) {
        printf("%d\n", data[i]);
    }
    free(data);
    return 0;
}

図 1 プログラム 1

図 2 data.txt

    int i, j, key, left, right, mid, target;

    for (i = 1; i < n; i++) {
        key = array[i];
        left = 0;
        right = i - 1;

        while (left <= right) {
            mid = (left + right) / 2;
            if (array[mid] > key) {
                right = 空欄[ (A) ];
            } else {
                left = 空欄[ (B) ];
            }
        }
        target = 空欄[ (C) ];

図 3 プログラム 2 の一部

题目描述

ANSI C 程序 1、2 从 data.txt 读取 $n\ge1$ 个整数，按升序排序并输出。程序 1 逐个取出 key，在线性扫描已排序前缀后移动元素并插入；程序 2 把定位插入位置的步骤改为二分查找。完整代码和示例输入见上文。

关于程序 1：
1. 对示例输入，求第 20 行第三次执行后 array[0] 至 array[4]；
2. 重排五个输入元素，使第 18 行的执行次数最大，并给出文件内容；
3. 从给定选项中选择最坏时间复杂度并说明理由。
关于程序 2：
1. 填写二分查找中的 A、B、C，完成左右边界和插入位置计算；
2. 选择修改后整个排序的最坏时间复杂度并说明理由；
3. 设图 3 第 10 行在整个执行中运行 $c$ 次，且元素互不相同。给出一种使 $c$ 最小的输入次序所满足的条件；
4. 用 $n$ 表示 $c$ 的最小值，并写出推导过程。

Kai

(1)

(1-1)

1回目: 4 8 5 1 2 
2回目: 4 5 8 1 2 
3回目: 1 4 5 8 2 
4回目: 1 2 4 5 8 

(1-2)

(1-3)

$O(n^2)$

Inner loop 1: $O(\text{target})$
Inner loop 2: $O(i - \text{target})$
$\Rightarrow$ Inner loop: $O(i)$

Therefore, the time complexity is $O(1) + O(2) + \cdots + O(n-1) = O(n^2)$

(2)

(2-1)

空欄[ (A) ]: mid - 1
空欄[ (B) ]: mid + 1
空欄[ (C) ]: left or right + 1

(2-2)

$O(n^2)$

The worst case time complexity of inner loop 2 is $O(i)$ .

(2-3)

The line mid = (left + right) / 2, uses integer division, which always rounds down (floor). This creates an asymmetry in how the search range collapses, i.e., since mid is biased towards the left (due to rounding down), updating right to mid - 1 shrinks the search interval more aggressively.

Hence when array[mid] > key is always true, the number of iterations of while loop is minimized, i.e., the while loop performs the minimum number of total iterations when the array is in descending order.

(2-4)

The number of iterations of the while loop required for a specific $i$ is exactly $\lfloor \log_2 (i+1) \rfloor$ .

Hence the result is

c = \sum_{i=1}^{n-1} \lfloor \log_2 (i + 1) \rfloor

\begin{aligned} c = \sum_{j=2}^{n} \lfloor \log_2 j \rfloor \end{aligned}

Knowledge

Actually there is a closed-form of the answer of (2-4), let us find it out.

Let

c_n = \sum_{j=2}^{n} \lfloor \log_2 j \rfloor = \sum_{j=1}^{n} \lfloor \log_2 j \rfloor

First we observe that

\begin{aligned} \lfloor \log_2(1) \rfloor &= 0 \\ \lfloor \log_2(2) \rfloor &= 1 \\ \lfloor \log_2(3) \rfloor &= 1 \\ \lfloor \log_2(4) \rfloor &= 2 \\ \lfloor \log_2(5) \rfloor &= 2 \\ \lfloor \log_2(6) \rfloor &= 2 \\ \lfloor \log_2(7) \rfloor &= 2 \\ \end{aligned}

In particular, notice that

\begin{aligned} c_3 &= 2 \times 1 \\ c_7 &= c_3 + 4 \times 2 \\ c_{15} &= c_7 + 8 \times 3 \\ &\cdots \end{aligned}

So we get (by induction)

c_{2^k - 1} = \sum_{j=1}^{k-1} 2^j \cdot j = 2^k k - 2^{k+1} + 2

This inspires the following. Let $k$ be a positive integer such that $2^k < n < 2^{k+1}$ . Then

c_n = c_{2^k-1} + \sum\limits_{j=2^k}^n \lfloor \log_2(j) \rfloor = c_{2^k-1} + (n - 2^k + 1) \cdot k = nk - 2^{k+1} +k+2

which is

c_n = (n+1)\lfloor \log_2 n \rfloor - 2^{\lfloor \log_2 n \rfloor + 1} + 2

Author​

Description​

図 1 プログラム 1​

図 2 data.txt​

図 3 プログラム 2 の一部​

题目描述​

Kai​

(1)​

(1-1)​

(1-2)​

(1-3)​

(2)​

(2-1)​

(2-2)​

(2-3)​

(2-4)​

Knowledge​