跳到主要内容

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

标签：

Author​

GPT-5.6 Sol, 祭音Myyura

Description​

図 1 に示す関数 sub(int data[], int digit) は基数ソートのコードの一部である。この関数の引数である配列 data の各要素は正整数であり、配列のサイズは NN である。関数 val(int i, int j) は、整数 ii の第 jj 桁目（j=0,1,…j=0,1,\ldots、最下位桁を 0 桁目とする）の数（0 から 9 の値を取る）を返す。配列の添字は 0 から始まることに注意し、次の (1) から (5) に答えよ。

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 の疑似コード

(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)(i,j) の組を答えよ。

(4)​

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

(5)​

以下ではデータ数を NN とし、入力は KK 桁の 10 進正整数とする。次の問いに答えよ。

  • (ア) 関数 sub の実行時間を NN と KK の関数 ff として表す。ff を big-O 表記で表せ。ただし、タイトな漸近的時間計算量を答えること。
  • (イ) 基数ソートアルゴリズム全体の計算量を NN と KK の関数 gg として表す。gg を big-O 表記で表せ。ただし、タイトな漸近的時間計算量を答えること。
  • (ウ) このソーティングアルゴリズムに必要なメモリビット数を NN と KK の関数 hh として表す。hh を big-O 表記で表せ。ただし、タイトな漸近的メモリビット数を答えること。

Kai​

(1)​

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

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

である。

(2)​

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

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

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

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

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

(3)​

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

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

である。

(4)​

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

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

(5)​

(ア)​

バケットの初期化は 10 回で定数時間、格納は NN 回、取り出しも全バケットの合計で NN 回である。したがって、

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

である。

(イ)​

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

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

である。

(ウ)​

KK 桁の整数一つの表現には Θ(K)\Theta(K) ビットが必要である。data および buf[10][N] が保持する整数の個数はともに Θ(N)\Theta(N) であり、ctr や添字変数に必要なビット数はこれより低次である。したがって、

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

である。

検算​

一時プログラムで各バケットを入力順のリストとして実装した。sub(data, 0) 後のバケット 7 が [637, 127]、127127 の位置が (7, 1)、出力が [211, 214, 415, 637, 127] となることを確認した。さらに 0、1、2 桁目を順に処理すると [127, 211, 214, 415, 637] となり、各回で同じ桁値の相対順序が保存されることも確認した。

本页目录