バイキングで食事をするとき，若い頃は何も考えずにお皿にどんどん乗せていました。少々無理に盛っても，気合いで食べきっていました。元を取ってやろうとか，元以上に食べてやろうとか，そんな不純な気持ちもありましたし。しかし，このごろ，油ものや炭水化物を控えめにし，更に皿の大きさから自分の食べられる量に見当をつけて取るようになりました。食べ残しをしたくない事もありますが，おなか周りの余剰財産をなんとか増やさないようにしたいのです。その思いはなかなか実らず，だぶついた財産は心肺機能を圧迫し続けています。

さて，見当を付ける，ということは何時でも大切なことです。しかし，プログラミングの初心者のうちは，見当の付けようが分からず，組んで動かしてみて初めてパフォーマンスの悪さに愕然としたりするものです。できるなら，コードを組む前に，少なくとも動かす前にはパフォーマンスの見当を付けたいものです。今回から学習する内容は，そのための強力な武器となります。

計算量とは

計算量（※1）とは，あるアルゴリズムを実行するとき，最大でどれだけ大変なことになるかを表す量です。元の英語を直訳すると「計算の複雑さ」となり，この方が意味をよく実感出来ます。

一言でまとめるために「どれだけ大変なことになるか」なんて，ちょっと曖昧な言葉を使いました。具体的には計算量は時間計算量（※2）と領域計算量（※3）に分けられます。

いくら大型コンピュータを使っているとはいえ，実用的な時間内で実行終了出来なければ意味がありません。何を持って実用的とするかは，実行するプログラムや得られる結果の価値に応じて決まります。あるアルゴリズムAが別のアルゴリズムBより少ない手順で結果を得られるならば「アルゴリズムAの時間計算量がアルゴリズムBの時間計算量より小さい」と言うことが出来ます。

いくら高速に計算が出来るアルゴリズムでも，大量にメモリを消費すると，小さなコンピュータ，例えばパソコンでは実行できません。そのようなアルゴリズムは大型コンピュータで実行すべきです。大量にメモリを消費するアルゴリズムは，領域計算量が大きい，と言うことが出来ます。可能な限り，領域計算量の小さなアルゴリズムを選択するべきです。領域計算量が大きければ，実際のプログラムの実行時間のうちの多くの部分をメモリアクセスの時間で消費してしまうからです。

時間計算量も領域計算量も，実際に取り扱うデータの状態によって大きく変化する事がありますから，アルゴリズムが決まっても計算量はどちらも一意に決まりません。

このため，計算量を表すために，かちっと数式化したものを用いず，おおよそどれくらいの大きさになるかを用います。

この連載中では，計算量といえば時間計算量を指すものとします。領域計算量については取り扱いません。

※1）

computational complexity

※2）

Time complexity

※3）

space complexity

計算量の記号

おおよそどれくらい，という計算量を表すためにはオーダー表記を用います。

記号O ()をオーダー記号（※4）といいます。オーダー表記に単位はありません。例えば時間計算量の単位は秒でもないしクロック数でもありません。「あるアルゴリズムを実行するときの手順の数と繰り返しの数の合計」です。オーダーの違いというと，桁数の違いと直訳してしまいがちですが，実際には10進数や2進数といった基数の違いによって桁数はずいぶん変わりますから，桁数の違いだけでオーダーの違いを限定できません。計算量のオーダーは，1,n,log n,na,･･･といった具合に，式で表現します。たとえば，時間計算量O (1)は，入力の大きさに関わらず一定回数のアルゴリズム実行で終了するもののことです。O (n)は，入力の大きさnに対して，最大でおよそn回のアルゴリズム実行で終了するもののことです。目的が同じならば前者のアルゴリズムの方が優れていると言えます。O (n)のアルゴリズムだけに注目すると，nが大きいときと小さいときの実行時間の差がどれほどになるか見立てることができます。「nが倍の2nになると，実行時間は倍になるだろう」といった具合です。

これがアルゴリズムをオーダー表記することの意味です。

※4）

order symbol. ランダウの記号（Landau symbol），ランダウのO-記法（Landau’sO-notation）ともいいます。