平成21年度秋期 応用情報技術者試験 午前 問5
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になる。実装方法2：ほぼ1になる。
- イ 実装方法1：ほぼ1になる。実装方法2：ほぼnに比例する。
- ウ 実装方法1：ほぼnに比例する。実装方法2：ほぼ1になる。
- エ 実装方法1：ほぼnに比例する。実装方法2：ほぼnに比例する。
解答・解説を見る
正解：イ
AI解説
frontのみを持つ実装方法1では末尾要素の削除は先頭から順にたどる必要がありg(n)はnに比例するが、末尾追加は末尾までたどる必要がありf(n)もnに比例するため両者の比はほぼ1になる。frontとrearを両方持つ実装方法2では追加f(n)はO(1)だが、削除は単方向リストのため末尾の一つ前の要素を探すのにO(n)かかりg(n)/f(n)はnに比例する。 ア: 実装方法2ではrearがあっても単方向リストでは末尾の一つ前を辿るのに時間がかかるため、g(n)/f(n)が「ほぼ1になる」とする記述は誤りである。 イ: 正しい。実装方法1ではf(n)・g(n)がともにnに比例するため比はほぼ1になり、実装方法2ではf(n)がO(1)なのに対しg(n)がO(n)のままなので比はnに比例する。 ウ: 実装方法1でg(n)/f(n)がnに比例するという記述は、追加も削除もほぼ同じ時間(nに比例)がかかるため比が1に近づく実態と矛盾する。 エ: 実装方法1・2ともに比がnに比例するという記述は、実装方法2でrearを使うことでf(n)がO(1)になる効果を無視しており誤りである。 💡 単方向連結リストでは末尾へのポインタ(rear)があっても「末尾の削除(一つ前の要素を探す)」は依然としてO(n)である点が引っかかりやすい。追加は速くなるが削除は速くならない、という非対称性を覚えておく。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。