名古屋工業大学 工学研究科 工学専攻 情報工学系 2019年8月実施 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

• 名古屋工业大学
• 基数排序
• 桶排序
• 算法复杂度

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

I　図1に示す関数 sub(int data[], int digit) は基数ソートのコードの一部である。なお，この関数の引数である配列 data の各要素は正整数であり，配列 data のサイズは $N$ である。関数 val(int i, int j) は，整数 $i$ の第 $j$ 桁目（$j=0,1,\ldots$，最下位桁を0桁目とする）の数（0から9の値を取る）を返す関数である。このとき，次の (1)〜(5) の問いについて答えよ。以下では配列の添字は0から始まることに注意せよ。

(1) 関数 sub を完成させるため，空欄 (A)，(B) に適切な内容を入れよ。

(2) 配列 data を

data[0] = 637; data[1] = 214; data[2] = 127;
data[3] = 415; data[4] = 211;

と初期化した上で，sub(data, 0) を実行した。実行後の配列 data の内容を {data[0], data[1], data[2], data[3], data[4]} という形式で示せ。

(3) (2) の状況（sub(data,0) の実行後）で buf[i][j]=127 となる $(i,j)$ の組を答えよ。

(4) 配列 data の各要素を3桁の正整数であると仮定する。sub を複数回呼び出すことで，data の内容を昇順にソーティングをしたい。sub の呼び出し側で必要となる疑似コードを図1の記述にならって書け。

void sub(int data[], int digit) {
    int buf[10][N], ctr[10];
    int i, j, k, t; t = 0;

    for (i = 0; i <= 9; i++) ctr[i] = 0;

    for (i = 0; i < N; i++) {
        k = val(data[i], digit);
        buf[k][ctr[k]] = data[i];
        ______(A)______;
    }

    for (i = 0; i <= 9; i++) {
        for (j = 0; j <= ctr[i] - 1; j++) {
            data[t] = ______(B)______;
            t++;
        }
    }
}

図1　関数 sub の擬似コード

(5) 以下では，データ数を $N$ とする。また，入力は $K$ 桁の10進正整数とする。以下の問い (ア)〜(ウ) を答えよ。

(ア) 関数 sub の実行時間を $N$ と $K$ の関数 $f$ として表す。関数 $f$ を big-O 表記（$O(\cdot)$ 表記）で表現せよ。ただし，big-O 表記においてはタイトな漸近的時間計算量を答えること。

(イ) 基数ソートアルゴリズム全体の計算量を $N$ と $K$ の関数 $g$ として表す。関数 $g$ を big-O 表記で表現せよ。ただし，big-O 表記においてはタイトな漸近的時間計算量を答えること。

(ウ) このソーティングアルゴリズムに必要なメモリビット数を $N$ と $K$ の関数 $h$ として表す。関数 $h$ を big-O 表記で表現せよ。ただし，big-O 表記においてはタイトな漸近的メモリビット数を答えること。

题目描述

I　图1的函数 sub(int data[], int digit) 是基数排序代码的一部分。作为参数的数组 data 各元素均为正整数，大小为 $N$。函数 val(int i, int j) 返回整数 $i$ 的第 $j$ 位数字（$j=0,1,\ldots$，最低位为第0位），返回值为0至9。请回答以下 (1) 至 (5) 问。注意数组下标从0开始。

(1) 为完成函数 sub，请在空格 (A)、(B) 填入适当内容。

(2) 将数组 data 初始化为

data[0] = 637; data[1] = 214; data[2] = 127;
data[3] = 415; data[4] = 211;

并执行 sub(data, 0)。请用 {data[0], data[1], data[2], data[3], data[4]} 的形式写出执行后数组 data 的内容。

(3) 在第 (2) 问的情况下，即执行 sub(data,0) 后，求使 buf[i][j]=127 的 $(i,j)$。

(4) 假设数组 data 的各元素都是三位正整数。希望多次调用 sub，将 data 按升序排序。请仿照图1的写法，写出调用 sub 一侧所需的伪代码。

void sub(int data[], int digit) {
    int buf[10][N], ctr[10];
    int i, j, k, t; t = 0;

    for (i = 0; i <= 9; i++) ctr[i] = 0;

    for (i = 0; i < N; i++) {
        k = val(data[i], digit);
        buf[k][ctr[k]] = data[i];
        ______(A)______;
    }

    for (i = 0; i <= 9; i++) {
        for (j = 0; j <= ctr[i] - 1; j++) {
            data[t] = ______(B)______;
            t++;
        }
    }
}

图1　函数 sub 的伪代码

(5) 下面设数据个数为 $N$，输入为 $K$ 位十进制正整数。回答 (ア) 至 (ウ) 问。

(ア) 将函数 sub 的运行时间表示为 $N,K$ 的函数 $f$。请以 big-O 记法（$O(\cdot)$ 记法）表示 $f$，要求给出紧的渐近时间复杂度。

(イ) 将整个基数排序算法的时间复杂度表示为 $N,K$ 的函数 $g$。请以 big-O 记法表示 $g$，要求给出紧的渐近时间复杂度。

(ウ) 将该排序算法所需的存储比特数表示为 $N,K$ 的函数 $h$。请以 big-O 记法表示 $h$，要求给出紧的渐近存储比特数。

Kai

(1)

要素をバケットへ追加した後、そのバケットの要素数を 1 増やす。取り出すときは、バケット番号 $i$ とバケット内添字 $j$ をそのまま用いる。したがって、

(A) ctr[k]++
(B) buf[i][j]

である。

(2)

1 の位ごとのバケットは、入力順を保って次のようになる。

buf[1] = [211]
buf[4] = [214]
buf[5] = [415]
buf[7] = [637, 127]

バケット番号 0 から順に連結するので、

$$\boxed{\{211,214,415,637,127\}}$$

となる。同じ 1 の位を持つ $637,127$ の順序が保たれており、この処理は安定である。

(3)

$127$ の 1 の位は 7 である。また、バケット 7 では $637$ が添字 0 に先に入るため、$127$ は添字 1 に入る。したがって、

$$\boxed{(i,j)=(7,1)}$$

である。

(4)

最下位桁から最上位桁へ順に、安定な sub を適用する。

for (digit = 0; digit <= 2; digit++) {
    sub(data, digit);
}

(5)

(ア)

val、整数の代入および添字演算をそれぞれ定数時間とする計算モデルで評価する。バケットの初期化は 10 回で定数時間、格納は $N$ 回、取り出しも全バケットの合計で $N$ 回である。したがって、

$$f(N,K)=\Theta(N),\qquad\boxed{f(N,K)=O(N)}$$

である。

(イ)

$K$ 個の桁について sub を 1 回ずつ呼ぶので、

$$g(N,K)=\Theta(NK),\qquad\boxed{g(N,K)=O(NK)}$$

である。

(ウ)

$K$ 桁の整数一つの表現には $\Theta(K)$ ビットが必要である。data および buf[10][N] が保持する整数の個数はともに $\Theta(N)$ であり、ctr や添字変数には $O(\log N+\log K)$ ビットが必要であり、$N,K\ge1$ ではこれも $O(NK)$ に収まる。したがって、

$$h(N,K)=\Theta(NK),\qquad\boxed{h(N,K)=O(NK)}$$

である。

Reference

• 公式原題（公式サイトの保存版）