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