平成21年度 秋期 午前 問5

✓ これが正解イほぼ 1 になる。 ほぼ n に比例する。

解説

末尾を指す変数があると、追加だけが速くなります。

連結リストは、各セルが値と次のセルへのポインタをもち、先頭から数珠つなぎに辿っていく構造です。先頭を指す変数だけをもつ実装では、末尾へ要素を足すにも、末尾の要素を消すにも、まず先頭から末尾まで辿る必要があります。どちらも同じだけ辿るので、二つの時間はほぼ同じ大きさになり、割り算した比は一定の値に近づきます。末尾を指す変数も併せもつ実装では、追加のほうは末尾に一足で届くので、要素数がいくら増えても時間はほとんど変わりません。ところが削除のほうは事情が違います。末尾を消したあと、新しい末尾となる一つ手前のセルを指し直さなければならず、ポインタが前向きにしか張られていないので、その一つ手前を探すには結局先頭から辿ることになります。分母だけが一定のまま分子が要素数とともに伸びるので、比は要素数に比例して大きくなります。

ほかの選択肢はなぜ違うのか

• アほぼ 1 になる。 ほぼ 1 になる。：二つの実装のどちらでも比が一定の値に近づく、としています。末尾を指す変数をもつほうは追加の側だけが一足で済むようになるため、二つの時間は釣り合わなくなります。
• ウほぼ n に比例する。 ほぼ 1 になる…：先頭だけをもつほうで比が要素数に比例し、末尾も指すほうで一定に近づく、としています。速くなるのは末尾を指す変数をもつ側なので、二つの実装の役割がそっくり入れ替わっています。
• エほぼ n に比例する。 ほぼ n に比例…：二つの実装のどちらでも比が要素数に比例する、としています。先頭だけをもつほうは追加も削除も同じだけ先頭から辿るので、割り算した値は伸びずに一定へ近づきます。