アルゴリズムの計算量とオーダー記法を読み解く

時間計算量は、入力サイズnが増えたとき、アルゴリズムが必要とする基本処理の回数がどの程度増えるかを表します。

実際の実行時間はCPU、メモリ、プログラム言語、コンパイラ、データ配置などに左右されます。そのためO(n)だから必ず何ミリ秒で終わる、という意味ではありません。

計算量の利点は、環境依存の秒数ではなく、入力が大きくなったときの伸び方を比較しやすいことです。

空間計算量は必要な追加メモリ量の増え方を表す別の尺度です。FEの現行シラバスでは時間計算量が代表用語ですが、アルゴリズム評価では時間とメモリの両面を考える場合があります。

入力サイズnが十分大きいとき、増加率を支配する項に注目します。例えば3n+10ではnの項が支配的なのでO(n)、2n²+5n+1ではn²が支配的なのでO(n²)と表します。

定数倍を無視するのは、nが大きくなったときに2nと100nがどちらもnに比例して増えるという性質を比較したいからです。実際の実行時間では定数倍も無視できない場合があります。

対数の底は定数倍の違いになるため、漸近的なBig OではO(log₂n)もO(log₁₀n)もO(log n)と表せます。

Big Oは『常に正確にこの回数で実行される』という等式ではなく、入力増加に対する代表的な上界の増え方を表す記法として読みます。

O(1)は入力サイズが増えても主要な処理回数がほぼ一定の処理です。添字を指定した配列アクセスなどが代表例です。

O(log n)は、1回処理するたびに対象範囲を半分にするような処理で現れます。二分探索が代表例です。

O(n)は全要素を一度ずつ確認するような処理、O(n²)はn回の処理をさらにn回繰り返す単純な二重ループなどで現れます。

O(n log n)は、問題を分割しながら各段階で全体に近い量の処理を行う効率的な整列アルゴリズムなどで現れます。

n回繰り返す一重ループの本体がO(1)なら、全体はO(n)です。

外側がn回、内側も各回n回実行される単純な二重ループなら、処理回数はn×nでO(n²)です。

O(n)の処理の後に別のO(n²)処理を実行する場合、合計はO(n+n²)ですが、大きなnではn²が支配するためO(n²)とします。

ループ変数を毎回2倍にする、あるいは対象を毎回半分にする処理では、nへ到達するまでの回数はおおよそlog₂n回なのでO(log n)になります。

線形探索は先頭から順に調べるため、最悪の場合はn個すべてを確認します。最悪時間計算量はO(n)です。

二分探索は、整列済みのデータに対して中央要素と比較し、次に調べる範囲を半分へ絞ります。そのため最悪でも比較回数はおおよそlog₂nに比例し、O(log n)です。

ただし二分探索を使うには、探索対象が順序付けられていて、中央付近の要素へ効率よくアクセスできることなどの前提があります。未整列データへそのまま適用することはできません。

一度だけ探索するために毎回ソートするなら、ソートに掛かるコストも含めて全体の処理量を考える必要があります。

選択ソートは、未整列部分から最小値などを探す処理を繰り返すため、代表的な時間計算量はO(n²)です。バブルソートも単純な実装ではO(n²)として扱われます。

マージソートはデータを分割し、それぞれを整列してマージする分割統治法のアルゴリズムで、時間計算量はO(n log n)です。

クイックソートは平均的にはO(n log n)ですが、分割の偏り方によって最悪O(n²)になる場合があります。

『ソートはO(n log n)』のように一括りにせず、アルゴリズムと、平均・最悪などどのケースを述べているかを確認します。

線形探索では、目的の値が先頭にあれば最良ではほぼ一定回数ですが、末尾や存在しない場合は最悪でn件を確認します。

アルゴリズムの説明でO(n)とだけ書かれている場合でも、どのケースを評価しているかを文脈から確認します。試験問題では『最悪の場合』『平均的に』などの条件が示されることがあります。

計算量を比較するときは、入力サイズnの定義も確認します。例えば行列の一辺をnとする場合と、全要素数をnとする場合では式の意味が変わります。