平成24年度 秋期 午前 問6

✓ これが正解イアルゴリズムがこれより遅くならないという計算量の上限値を表す。

解説

最悪でもこれくらい、という上限の見積りです。

オーダ記法が何を表すかを一言で言うと、処理にかかる手間の上限です。データの個数が増えたとき、かかる時間がどこまで伸びうるかを大づかみに示すもので、これより遅くはならないという天井を与えます。正解の肢は、まさにその上限という言い方をしています。もう少し丁寧に見ると、この記法には三つの約束があります。一つ目は、いま述べた上限を表すこと。二つ目は、定数倍の係数を落とすこと。三つ目は、最も大きく伸びる項だけを残し、それより小さい項を落とすことです。たとえば手間が 3 掛ける n の二乗に 5n と 100 を加えた式で表せるなら、書き表すのは n の二乗の部分だけになります。比べたいのはデータが増えたときの伸び方であって、実際の秒数ではないからです。この三つの約束のどこかを裏返すと、そのまま誤りの肢が作れてしまいます。設問が処理時間と計算時間の比較に限っている点にも注意してください。何を測っているのかという軸を取り違えると、正しそうに読める記述に引き寄せられます。

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

• アアルゴリズムが解に到達するまでの計算量の…：天井と床が入れ替わっています。ここに書かれているのは、これ以上は速くならないという下側の見積りで、別の記法が受け持つ役目です。設問の記法が示すのは上側の見積りです。
• ウアルゴリズムの解析では，主要項の部分を除…：残すものと捨てるものが逆になっています。伸び方を決めるのは最も大きく育つ項ですから、比較のときに残すのはそちらで、落とすのはそれ以外の項と定数倍の係数のほうです。
• エアルゴリズムを実現した場合の変数領域の大…：測る対象が違います。これは領域計算量、つまり記憶領域をどれだけ使うかという側の見積りにあたります。設問は処理時間と計算時間の比較に限っているので、軸が合いません。