問5
ｎ個の要素ｘ1,ｘ2,・・・,ｘnから成る連結リストに対して、新たな要素ｘn+1の末尾への追加に要する時間をｆ（ｎ）とし、末尾の要素ｘnの削除に要する時間をｇ（ｎ）とする。ｎが非常に大きいとき、実装方法１と実装方法２におけるｇ（ｎ）／ｆ（ｎ）の挙動として、適切なものはどれか。
|
|
実装方法１ |
実装方法２ |
○正解
×不正解
-
ほぼ１になる
ほぼ１になる
-
ほぼ１になる
ほぼｎに比例する
-
ほぼｎに比例する
ほぼ１になる
-
ほぼｎに比例する
ほぼｎに比例する
解説
実装方法1では新たな要素を追加する際にはfrontから最後のセルまで順に辿らなくてはならず、処理時間f(n) はn が増えるほど増加するのでn に比例することになります。同じように削除処理時間g(n)もｎが増えれば同様にn に比例するのでg(n)/f(n)はほぼ1になります。
実装方法2では追加の場合はrearのアドレス指定に従い1つ追加するだけなので処理時間はほぼ1になります。しかし削除する場合はrearからは1つ前のアドレスがわからないためfrontから順に辿ることになり作業時間g(n)はn に比例します。よってg(n)/f(n)はｎに比例します。