26.1.6.33 配列計算の計算量

コンピュータの特長の一つは大量のデータを高速に処理できることですが，コンピュータも無限に速いわけではないので，同じ問題を処理するのにも，やり方によって所要時間にかなりの差が出るのがふつうです．整列のアルゴリズムでも，単純な"Sort1"の方法と併合整列"SortM"の方法とでは能率がかなり違い，とくに扱うデータ量が多くなってくるとその差は禁止的に大きくなります．このような計算の手間を計算量と呼びます．もちろん，速いコンピュータを使えばそれだけ短い時間で計算が終りますが，アルゴリズム間の計算量の差(あるいは比)はもっと大きいのがふつうです．

計算量は，アルゴリズムの中の処理単位，たとえば四側演算や比較などの数ではかりますが，一般には“問題の大きさn”の関数の形になります．そして，その関数の項のうちで“全体の傾向を決める主要なもの”の関数形を使った議論がよく行なわれます．これをこの計算量のオーダと呼び0(n)，0(n2)などと表わします．これまでに扱ったいくつかのアルゴリズムについて，そのオーダを見てみましょう．

まず単純な探索ですが，これは端から順に調べてゆくわけですから，要素数をn，どこで見つかるかが等確率だとすれば，平均的にはn/2回の判定で終了します．つまりオーダn，0(n)と言うことができます．日本語入力を行なう場合の「かな漢字変換」では“よく探される要素を前の方へ移す”ことによって，能率を高めるくふうをしていますが，原理的にはこのオーダの手間がかかります．