擬似言語の計算量（オーダー）とは？ループの回数から処理の速さを見積もる考え方を解説

計算量と言われても、何をどう数えればいいのか分からない。

問題文にオーダーという言葉が出てきて、手が止まったことはありませんか？

n の2乗、log n。記号だけを見ると数学の話に見えて、身構えてしまう人は多いです。

でも大丈夫です。計算量は、処理が何回繰り返されるかを数えているだけの話です。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、データが1000件のうちは快適だった画面が、10万件を超えた途端に返ってこなくなる場面を何度も見てきました。

そのとき効くのが、コードを見て回数を見積もる目です。試験で問われているのも、まさにこの目のことでしょう。

この記事では、擬似言語のコードから計算量を読み取る手順を、初歩から順に組み立てていきます。

計算量とは処理の回数を数えること¶

はじめに、言葉の意味をそろえておきましょう。計算量とは、あるアルゴリズムが答えを出すまでにかかる手間を表したものです。

ここでいう手間は、秒ではありません。比較や代入といった処理を何回行うか、その回数で測ります。

なぜ秒で測らないのでしょうか。同じプログラムでも、動かす機械が違えば速さが変わってしまうからです。

回数で測れば、機械の性能に左右されずにアルゴリズムそのものを比べられます。試験で実行回数を問う問題が多いのは、このためです。

データが増えたときの伸び方を見る¶

計算量で本当に知りたいのは、一回あたりの速さではありません。データが増えたときに、手間がどう伸びるかです。

データの件数を n と置いてみます。n が2倍になったとき、処理の回数も2倍で済むのか、それとも4倍に膨らむのか。

この伸び方こそが、アルゴリズムの性格を決めます。件数が小さいうちは、どんな方法でも一瞬で終わるので差が出ません。

差がはっきり出るのは、n が大きくなってからです。だから計算量の話では、n が十分に大きい場合を想定します。

細かい定数は切り捨てて考える¶

伸び方だけを見るので、細かい数はあまり気にしません。処理が 2n 回でも 2n + 5 回でも、n に比例するという性格は変わらないからです。

こうした大づかみな表し方をオーダーと呼び、O(n) のように書きます。O は、だいたいこの伸び方だと示すための記号だと思ってください。

n が10万のとき、プラス5という差は誤差にしかなりません。一方で n と n の2乗の差は、そのまま10万倍に広がります。

だから定数は落とし、いちばん大きく伸びる部分だけを残します。この割り切りこそが、計算量を怖くなくしている正体です。

ループの形を見れば計算量は分かる¶

ここからが実戦です。擬似言語のコードから計算量を求める作業は、ループの重なりを数える作業とほとんど同じだと考えてください。

代表的な三つの形を、順に見ていきましょう。

一重のループは n に比例する¶

まずは、いちばん単純な形からです。配列の要素を先頭から順に1回ずつ見ていく処理を考えます。

○整数型: i, 合計
○整数型の配列: data ← {4, 8, 15, 16, 23, 42}

合計 ← 0
for (i を 1 から data の要素数 まで 1 ずつ増やす)
  合計 ← 合計 + data[i]
endfor

このループは、要素数の分だけ回ります。要素が6個なら6回、n 個なら n 回です。

中身は1回ぶんの足し算だけなので、全体の手間は n に比例します。オーダーで書けば O(n) です。

ループの回数がそのまま計算量になる、もっとも素直な形といえます。

配列の添字と要素数の関係があいまいなままだと、この数え方でつまずきます。心当たりがあれば先にこちらで土台を固めておいてください。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

二重のループは n の2乗になる¶

次は、ループの中にループがある形です。ここが計算量の大きな分かれ目になります。

外側が n 回まわり、そのたびに内側が n 回まわる。掛け算になるので、合計は n × n 回です。

○整数型: i, j

for (i を 1 から n まで 1 ずつ増やす)
  for (j を 1 から n まで 1 ずつ増やす)
    /* ここが n × n 回実行される */
  endfor
endfor

これが O(n の2乗) です。n が10なら100回ですが、n が1000になると100万回まで膨れ上がります。

伸び方の激しさが伝わるでしょうか。データが10倍になると、手間は100倍になる計算です。

内側の回数が外側の進み具合に応じて短くなる書き方もあります。その場合でも全体はおよそ半分なので、定数を落とすと O(n の2乗) のままです。

入れ子のループを追う手順そのものに不安があるなら、こちらで確認しておくと数えやすくなります。

【関連記事】擬似言語の多重ループ（入れ子の繰返し）がわからない人へ｜二重forの読み方を解説

半分ずつ減らす処理は log になる¶

もう一つ、試験でよく出る形があります。1回の処理で、調べる範囲が半分になっていくものです。

範囲が1になるまで、何回半分にできるか。それがそのまま回数になります。

n が8なら、8から4、4から2、2から1で3回です。n が1024まで増えても、10回で終わります。

この伸び方を O(log n) と書きます。データが1000倍になっても、回数は10回ぶんしか増えません。

半分ずつ減らす代表が二分探索です。その動きは、こちらの記事で一行ずつ追っています。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

よく出る計算量を並べて比べる¶

言葉だけでは差が実感しにくいところです。代表的なオーダーを、速い順に一覧にしてみます。

下にいくほど、データが増えたときの苦しさが増します。同じ1000件でも、O(1) と O(n の2乗) では100万倍の開きがあります。

注目してほしいのは O(log n) の行です。1000件を10回で片づけるのですから、二分探索がなぜ強いのかが数字で分かります。

いちばん大きい項だけが残る¶

一つの処理の中に、O(n) のループと O(n の2乗) の二重ループが両方あるとします。このとき全体の計算量はどうなるでしょうか。

答えは O(n の2乗) です。足し合わせたとき、いちばん大きく伸びる項だけが結果を決めます。

n が1000なら、1000回と100万回を足して100万1000回。ほぼ100万回と変わりません。

コードを読むときは、いちばん深く重なっているループを探してください。そこが全体の計算量を決めています。

時間だけでなく場所の話もある¶

ここまで見てきたのは、処理にかかる時間のほうの計算量です。実はもう一つ、使うメモリの量に注目した見方もあります。

こちらは、作業用にどれだけの入れ物を用意するかで測ります。変数を数個使うだけなら O(1)、元と同じ大きさの配列をもう一本用意するなら O(n) です。

処理を速くするために、余分な配列を用意することがあります。時間を縮めるかわりに場所を使う、という取引です。

科目Bで正面から問われる場面は多くありません。ただ、なぜこの配列を用意しているのかを考えるときの手がかりになります。

科目Bでは実行回数として問われる¶

試験でオーダーの記号がそのまま問われることは、それほど多くありません。かわりに、この処理は何回実行されるかという形で問われます。

つまり、やることは回数の数え上げです。身構えずに、ループの範囲を読み取っていきましょう。

探索の比較回数は場合によって変わる¶

線形探索を例にします。配列を先頭から順に調べ、探したい値が見つかった時点で止まる処理です。

この比較回数は、値がどこにあるかで変わります。場合分けして表にまとめます。

問題文に最悪の場合と書いてあれば、答えは n 回です。平均を問われたら、およそ半分と答えます。

どの場合を聞かれているのかは、問題文に必ず書いてあります。そこを読み飛ばすと、正しく数えたのに選択肢が合わないという事故が起きます。

ここで大事なのは、平均でもオーダーは O(n) だという点です。2で割った定数は、伸び方を変えないからです。

繰返しの終わり方を読み違えると、この回数はすぐにずれます。while と for の止まり方があいまいな人は、こちらを確認してみてください。

【関連記事】擬似言語のwhileとforってどう違う？繰返し処理で迷子にならない方法を詳しく解説

整列の比較回数は二重ループから求める¶

整列の問題でも、比較回数はよく問われます。選択ソートを思い出してください。

1周目は n − 1 回、2周目は n − 2 回と、比べる相手が1つずつ減っていきます。全部足すと n × (n − 1) ÷ 2 回です。

n が10なら45回、n が100なら4950回になります。ざっくり n の2乗の半分だと覚えておけば十分でしょう。

定数の2分の1を落とすと、オーダーは O(n の2乗) です。効率のよい整列が O(n log n) と言われるのは、この二乗を避けているからです。

選択ソートの動き自体をまだ追い切れていないなら、こちらの記事が土台になります。

【関連記事】擬似言語の整列（ソート）がわからない人へ｜選択ソートと交換処理の読み方を解説

数えるときにつまずきやすい場所¶

最後に、実際に回数を数えるときの注意点を二つ挙げておきます。どちらも私が相談を受けてきた中で目立ったものです。

一つ目は、ループの範囲の読み違いです。1 から n までなら n 回ですが、2 から n までなら n − 1 回になります。

端の1回ぶんは、選択肢の差になりやすい部分です。範囲の書き方は必ず声に出して確かめてください。

二つ目は、ループの外にある処理を数に入れてしまうことです。ループの前後で1回だけ動く初期化や表示は、n が増えても増えません。

だから、それらは定数として落とせます。数えるべきなのは、ループの中で n に応じて増える部分だけです。

見分け方は単純で、ループの中に入っているかどうかを見るだけです。字下げの位置をたどれば、どこまでが繰り返される範囲なのかがはっきりします。

とはいえ、慣れないうちは実際に小さな n で動かしてみるのがいちばん確実でしょう。n を3や4に置いて、手を動かして数えてみてください。

Giji Academy の擬似言語シミュレーターなら、ループが何周したかを目で追いながら処理を確かめられます。二重ループの回数が本当に掛け算になっているか、自分の目で確認できると納得の度合いが違います。

まとめ¶

ここまで確認したことを振り返ります。

計算量は、処理が何回行われるかで手間を測る考え方でした。秒で測らないのは、機械の性能に左右されないためです。

細かい定数は落とし、n が増えたときの伸び方だけを見ます。この大づかみな表し方がオーダーで、O(n) のように書きます。

コードから計算量を読むときは、ループの重なりを見てください。一重なら O(n)、二重なら O(n の2乗)、半分ずつ減るなら O(log n) が目安になります。

科目Bでは、オーダーの記号よりも実行回数そのものが問われます。線形探索の最悪は n 回、選択ソートは n × (n − 1) ÷ 2 回でした。

複数の処理が並んでいるときは、いちばん大きく伸びる項だけが残ります。深く重なったループを探せば、全体の計算量が見えてきます。

回数を数える作業は、結局のところトレースの延長線上にあります。値を追う手順に不安が残っているなら、こちらを先に固めておくと計算量も読みやすくなります。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

計算量は、覚える公式ではなく数える習慣です。今日の一問から、ループを見つけたら何回まわるかを声に出してみてください。