平成21年秋期 午前問5

アルゴリズムで行う演算問題。
ポインタに対する理解が鍵。
てか、PHPでポインタを意識することなんてほぼないんで!
分からんw!

実装方法1:
追加時間f(n)はn+1、削除時間g(n)はn。
故にg(n)/f(n)=n/n+1となるが、nは非常に大きいので
n/n+1≒n/n=1
となり、ほぼ1になる。

実装方法2:
変数rearから末尾のセルへ移動できても、「末尾のセルからその一つ手前のセルへはポインタがないので戻ることができない」という点に注意。

追加時間f(n)は1、削除時間g(n)はn-1。
故にn-1/1≒n/1=nとなり、ほぼnとなる。