転んでも転んでも立ち上がる 諦めないための記録

諦めないために学習記録を残しています。日商簿記検定・情報処理技術者試験の勉強記録が多いです。

 n 個の要素 x1,x2,…,xn から成る連結リストに対して,新たな要素 x[n + 1]
の末尾への追加に要する時間を f(n) とし,末尾の要素 xn の削除に要する時間を
g(n)とする。n が非常に大きいとき,実装方法 1 と実装方法 2 における
g(n) / f(n) の挙動として,適切なものはどれか。

[実装方法 1]

 先頭のセルを指すポインタ型の変数 front だけをもつ。
    ┌─┐  ┌─┬─┐  ┌─┬─┐       ┌─┬─┐
 front |●┼─>|x1|●┼─>|x2|●┼─> … ──>|xn|/|
    └─┘  └─┴─┘  └─┴─┘       └─┴─┘


[実装方法 2]

 先頭のセルを指すポインタ型の変数 front と,末尾のセルを指すポインタ型の
変数 rear を併せもつ。

    ┌─┐  ┌─┬─┐  ┌─┬─┐       ┌─┬─┐
 front |●┼─>|x1|●┼─>|x2|●┼─> … ──>|xn|/|
    └─┘  └─┴─┘  └─┴─┘      ┐└─┴─┘
    ┌─┐                   /
 rear |●┼──────────────────/
    └─┘

   ┌──────────┬──────────┐
   │   実装方法 1   │   実装方法 2   │
┌──┼──────────┼──────────┤
│ ア │ほぼ 1 になる。   │ほぼ 1 になる。   │
├──┼──────────┼──────────┤
│ イ │ほぼ 1 になる。   │ほぼ n に比例する。 │
├──┼──────────┼──────────┤
│ ウ │ほぼ n に比例する。 │ほぼ 1 になる。   │
├──┼──────────┼──────────┤
│ エ │ほぼ n に比例する。 │ほぼ n に比例する。 │
└──┴──────────┴──────────┘