問題
n個の要素x1，x2，…，xnから成る連結リストに対して，新たな要素xn+1の末尾への追加に要する時間をf(n)とし，末尾の要素xnの削除に要する時間をg(n)とする。nが非常に大きいとき，実装方法1と実装方法2におけるg(n)/f(n)の挙動として，適切なものはどれか。
〔実装方法1〕先頭のセルを指すポインタ型の変数frontだけをもつ。
〔実装方法2〕先頭のセルを指すポインタ型の変数frontと，末尾のセルを指すポインタ型の変数rearを併せもつ。
選択肢
- 1実装方法1：ほぼ1になる。／実装方法2：ほぼ1になる。
- 2実装方法1：ほぼ1になる。／実装方法2：ほぼnに比例する。
- 3実装方法1：ほぼnに比例する。／実装方法2：ほぼ1になる。
- 4実装方法1：ほぼnに比例する。／実装方法2：ほぼnに比例する。
正解
2. 実装方法1：ほぼ1になる。／実装方法2：ほぼnに比例する。
詳しい解説を見る解説を閉じる
解説
単方向連結リストの末尾削除g(n)は，直前の要素を探すため先頭から辿る必要があり，どちらの実装でもO(n)となる。末尾追加f(n)は，frontだけの実装方法1では末尾まで辿るためO(n)，rearをもつ実装方法2では一定時間O(1)。よって比g(n)/f(n)は，実装方法1ではO(n)/O(n)でほぼ1，実装方法2ではO(n)/O(1)でほぼnに比例する。（出典: 平成21年度 秋期 応用情報技術者試験 午前 問5）
一問一答
全400問を繰り返し学習