跳到主要内容

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

Author​

祭音Myyura, KardeniaPoyu

Description​

ANSI-C 準拠である C 言語のプログラム 1, 2 は、データを読み込んで、要素を昇順に整列して出力する。 入力するデータは、1 行目に整列する要素の個数 が、また 2 行目から 行目までに整列する要素として整数が各行に並べられた構造を持つ。 データは、ファイル 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) 整列する要素の個数を とするとき、プログラム 1 の 最悪時間計算量のオーダー表記として最も適しているものを下記選択肢から一つ選び、簡潔に理由も示せ。

                                          

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

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

                                          

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

5
8
4
5
1
2

図 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 の一部
​

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)​

5
8
5
4
2
1

(1-3)​

  • Inner loop 1:
  • Inner loop 2:
  • Inner loop:

Therefore, the time complexity is

(2)​

(2-1)​

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

(2-2)​

The worst case time complexity of inner loop 2 is .

(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 is exactly .

Hence the result is

or

Knowledge​

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

Let

First we observe that

In particular, notice that

So we get (by induction)

This inspires the following. Let be a positive integer such that . Then

which is

目录