基本情報の計算量とオーダーの求め方をループの例題で解説

基本情報の計算量は、ループの段数だけでは決まりません。入力の大きさをnとして、注目する処理が合計何回動くかを求め、その回数の増え方をO(n)やO(n²)で表すのが基本です。二重ループでも、内側が固定回数ならO(n)、変数が倍々に増えるならO(n log n)になることがあります。

大切なのは、初期値・更新式・終了条件を読み、内側の変数を毎回初期化するかまで確かめることです。この記事では、独自の擬似コードを使い、正確な繰返し回数とオーダー記法を分けて求める練習をします。探索法やソート名を覚えていても、初めて見るコードで手が止まる人向けの解説です。

基本情報の計算量とオーダーの基本

時間計算量は何の増え方か

時間計算量は、入力が大きくなったとき、必要な処理の量がどう増えるかを表すものです。配列の全要素を調べるなら、nは配列の要素数です。文字列を走査するなら文字数、整数nまで順に処理するならその上限値が、ここでの入力サイズになります。何をnと呼ぶのかを最初に決めましょう。

たとえば、配列の各要素を1回ずつ比較する処理では、要素数が4個なら4回、40個なら40回、400個なら400回の比較が必要です。この比較回数はnなので、時間計算量のオーダーはO(n)です。Oは数字のゼロではなく、アルファベットの大文字のオーです。

一方、処理回数が4n＋9なら、nが大きくなるほど定数9の影響は相対的に小さくなります。4という係数も除き、増え方をO(n)とまとめます。2n²＋7n＋12なら、主に増加を支配するのはn²の項なのでO(n²)です。係数や小さな項を落とすのは、回数を求めたあとに行います。

厳密には、O記法は十分大きなnに対する増え方の上限を表します。O(n)で抑えられる処理はO(n²)という緩い上限でも抑えられますが、基本的なオーダー判定では、その処理を適切に表す増え方を選びます。本記事もこの意味でO(n)などを使います。数学的な定義はNISTのO記法の説明で確認できます。

オーダーは秒数ではありません。O(n)と分かっても、100件の処理が何秒で終わるかは、機器・処理内容・実装によって変わります。また、同じO(n)でも1件あたりの仕事が違えば実時間は違います。試験問題の「実行回数」「比較回数」「計算量」のどれを問われているかを読み分けることが必要です。

オーダー	処理回数の例	nが大きいときの特徴
O(1)	入力件数によらず5回	一定の範囲に収まる
O(log n)	2倍・半分の操作を繰り返す	増加が緩やか
O(n)	n回、4n＋9回	入力に比例する
O(n log n)	n回それぞれで対数回の処理	線形より増えやすい
O(n²)	n²回、n(n−1)/2回	二次の項が支配する

表は処理量の増え方を整理したものです。小さい入力でも必ず上の行が速いという保証ではありません。nが2倍なら、nの項は2倍、n²の項は4倍になりますが、定数項や測定条件を含む実時間が同じ倍率になるとは限りません。

回数を求める四つの手順

擬似コードを読むときは、まず数える対象に印を付けます。以下の例題では、主にcountを1増やす文の実行回数を数えます。加算・比較・配列要素の参照は、それぞれ入力サイズによらない一定時間の操作として扱います。長い文字列の比較や配列全体の複製まで、無条件に1回と数える前提ではありません。

• nが何を表すか、初期値と数える対象を決める
• 条件が真の間に変数が取る値を小さいnで並べる
• 前後に続く処理は足し、入れ子は各回の内側の回数を合計する
• 回数の式を整理し、最も増える項からオーダーを選ぶ

たとえばiを1からnまで1ずつ増やすなら、iは1、2、…、nの値を取ります。両端を含むのでn回です。0からnまでならn＋1回、1からn−1までならn−1回になります。どれもオーダーはO(n)ですが、実行回数の選択肢としては同じではありません。

whileは条件を先に調べる繰返しなので、最初から条件が偽なら本体は0回です。n回本体を実行して普通に終了するwhileなら、最後の偽を含む条件判定はn＋1回になります。途中でreturnして抜ける場合は、その終了経路に応じて別に数えます。本体回数を聞かれているのに、終了判定まで足さないようにしてください。

本記事のforは、始点・終点を含み、明示した増分で進むものとします。コードは学習用の独自例で、試験の原文ではありません。実際の問題では注記を優先し、記号の意味はIPAの試験要綱・シラバスページにある擬似言語の記述形式で確認してください。

小さいnを代入するのは、一般式を探すための足場です。n＝1だけだとnとn²が同じ1になり、違いを見落とします。n＝4で動きを確かめ、n＝8に増やしたらどう変わるかも考えると、単に見た回数を暗記するより一般化しやすくなります。

一重ループと逐次処理を数える

最初は、n個の要素に対して同じ処理を1回ずつ行う例です。countの初期化は1回だけで、注目する加算はforの本体にあります。nは正の整数とします。

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    count ← count + 1
endfor

iが1、2、3、4なら、加算は4回です。一般にはn回なのでO(n)になります。条件判定やiの更新まで処理全体として数えると係数や定数が増えますが、各回の仕事が一定量なら、全体もnに比例して増えるためO(n)です。

増分が2になった場合も、値の変化を並べれば解けます。1からnまで2ずつ増やすなら1、3、5、…と進み、本体回数はn/2を切り上げた値です。n＝8なら4回、n＝9なら5回です。半分の件数を調べるだけなので、オーダーは依然としてO(n)になります。

次は二つのループが前後に並ぶ例です。最初のループが終わってから次が始まり、片方の内部で片方を繰り返す構造ではありません。

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    count ← count + 1
endfor
for (j を 1 から n まで 1 ずつ増やす)
    count ← count + 1
endfor

加算はn＋n＝2n回です。ループが二つあるからn²という判断は誤りで、逐次処理では回数を足します。n回の走査のあとにn²回の比較を行うなら、合計n＋n²からO(n²)になります。前後の処理のうち、入力を増やしたとき最も大きくなる項を見るわけですね。

固定100回のループを1回だけ行うなら、入力のnによらずO(1)です。「ループがあるからO(n)」とも決められません。ただし、100という数字が実は配列の最大件数を表し、問題が件数n一般について聞いているなら、その前提を確認します。固定値なのか入力由来の値なのかで答えが変わります。

二重ループは内側の条件まで読む

外側がn回で、そのたびに内側もn回ずつ動くときは、回数を掛け算できます。内側のjが外側の各回で1から始まることが、ここでの重要な条件です。

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    for (j を 1 から n まで 1 ずつ増やす)
        count ← count + 1
    endfor
endfor

n＝4なら、i＝1で4回、i＝2で4回、i＝3で4回、i＝4で4回です。合計16回、一般にはn×n＝n²回になります。外側が8回、内側も8回なら64回なので、入力が2倍になると注目する加算回数は4倍です。時間計算量はO(n²)です。

ところが、内側が1から3まで固定なら、外側の各回で行う仕事は3回です。合計3n回なのでO(n)になります。同じ二重ループでも、内側の上限がnか定数3かで増え方が違います。「二重」という見た目だけでは答えを選べない理由です。

内側の上限が外側のiに応じて変わる場合は、単純な同じ回数の掛け算を避け、各回の反復数を並べます。次はjを1からiまで動かす例です。

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    for (j を 1 から i まで 1 ずつ増やす)
        count ← count + 1
    endfor
endfor

外側iの値	内側jの値	加算回数
1	1	1
2	1、2	2
3	1、2、3	3
4	1、2、3、4	4

n＝4なら1＋2＋3＋4＝10回、一般には1＋2＋…＋n＝n(n＋1)/2回です。式を展開するとn²/2＋n/2なので、増え方はO(n²)になります。三角形の範囲しか動かないからO(n)になる、ということではありません。n²より少なくても、二次の項が残るためです。

もしjをi＋1からnまで動かすなら、各回はn−1、n−2、…、0回です。合計はn(n−1)/2回で、やはりO(n²)ですが、先ほどのn(n＋1)/2とは違います。同じオーダーでも、対角部分を含めるかで正確な回数が変わります。回数問題では最初と最後の行を必ず確認しましょう。

整列中の比較対象がどのように減るかを読みたい場合は、ソートアルゴリズムの種類と配列の動きも参考になります。このページでは名前ごとの暗記を広げず、与えられたループから式を作ることに集中しましょう。

倍増するループは対数回になる

whileの変数が1ずつ増えるとは限りません。次は、kを1から始め、毎回2倍にする例です。条件はkがn以下である間とします。

count ← 0
k ← 1
while (k ≦ n)
    count ← count + 1
    k ← k × 2
endwhile

n＝16なら、本体に入るときのkは1、2、4、8、16です。加算は5回で、更新後のk＝32は条件を満たさず本体に入りません。n＝32なら1、2、4、8、16、32の6回です。上限が2倍になっても回数は1回増えるだけになります。

一般には、2の何乗までn以下かを数えます。nが1以上の整数なら、加算回数はlog₂ nの小数点以下を切り捨てて1を足した値です。n＝16でlog₂16＝4なのに本体が5回なのは、k＝1の回も含むためです。正確な回数の「＋1」と、オーダーO(log n)を混同しないでください。

条件をk＜nに変えると、n＝16では16の回が消えて4回になります。オーダーは変わりませんが、本体回数は変わります。また、kを0から始めて2倍しても0のままです。終了へ向かって進まないコードには、通常の有限のループ回数を当てはめられません。

この倍増ループを、n回のforの内側に置き、外側の毎回でkを1へ戻すなら、合計はn×（log₂ nを切り捨てて1を加えた値）です。各回が同じ対数回なのでO(n log n)となります。二重ループからO(n²)以外が出る、もう一つの代表例です。

log₂nは「2を何乗するとnになるか」です。O(log n)で底を省略できるのは、2や10など固定された底の違いが定数倍に相当するためです。2、4、8と増える例では底2を使うと正確な回数を考えやすく、オーダーにまとめる段階で省略できます。

半分ずつ減る処理も同じ発想で読めます。n＝16を16、8、4、2、1と減らし、1より大きい間だけ処理すれば4回です。探索範囲の更新と合わせて理解したい人は、線形探索・二分探索の手順と比較回数で、実際に範囲が狭まる様子を確かめられます。

基本情報の計算量とオーダーを例題で求める

初期化の位置で合計回数が変わる

難しく見える二重ループでも、内側の変数が戻らず進み続けるなら、合計回数を直接数えられます。次はjの初期化がforの外にある例です。

count ← 0
j ← 1
for (i を 1 から n まで 1 ずつ増やす)
    while (j ≦ n)
        count ← count + 1
        j ← j + 1
    endwhile
endfor

n＝4なら、i＝1のときjは1、2、3、4と進み、加算4回のあとj＝5になります。i＝2でもjは5のままなのでwhileの条件は偽です。i＝3、4でも内側の本体は動きません。注目する加算は合計4回、一般にはn回です。

外側のループ自体もn回動き、各回でwhileの条件を確認します。内側の本体だけでなくこの管理処理を含めても、必要な仕事はnに比例する範囲なので、全体の時間計算量はO(n)になります。最初の回で全部進め、残りは条件確認だけという構造ですね。

j ← 1をforの内側、whileの直前へ移したら答えが変わります。外側のたびにjが1へ戻り、毎回n回の加算を行うので、合計n²回、O(n²)です。初期化の行をひとつ動かすだけで増え方が変わるため、問題のコードを省略して読まないことが大切です。

jの初期化位置	i＝1の内側回数	i＝2以降	合計の加算回数
外側forより前	n回	各0回	n回
外側forの本体	n回	各n回	n²回

もう少しずつ進む例として、条件がj≦iなら、i＝1でjを2へ、i＝2でjを3へ進めることになります。jを戻さないので、各iで1回ずつ、合計n回です。内側の終点が変わるから必ず三角形の和になるわけではありません。始点が毎回リセットされるかも、セットで読みましょう。

この見方は、二つの添字が一方向に進むコードでも役立ちます。「外側の回数×最大の内側回数」は上限の見積りとして使えても、実際より粗くなる場合があります。jが全体で何回増えるかという、コード全体を通した数え方へ切り替えると、過大なO(n²)判定を避けられます。

途中終了は最良・最悪を分ける

次は、配列Aの中から目的の値keyを探し、見つかった時点で戻る例です。配列の添字は1からnまでとし、1回の要素比較を一定時間とします。

for (i を 1 から n まで 1 ずつ増やす)
    if (A[i] ＝ key)
        return i
    endif
endfor
return 0

先頭で見つかるなら比較は1回、末尾で見つかるならn回、存在しない場合もn回です。したがって最良の場合はO(1)、最悪の場合はO(n)になります。途中終了が書かれているだけで、いつでもO(1)と判断することはできません。

平均を求める場合は、入力がどのように現れるかという前提が必要です。必ず1か所に見つかり、各位置が同じ確率で選ばれるなら、比較回数の平均は（1＋2＋…＋n）/n＝(n＋1)/2です。この条件では平均もO(n)です。見つからないケースの割合が違えば、正確な平均回数も変わります。

O記法という表記そのものが「最悪」を意味するわけではありません。最良の回数にO記法を使うこともできます。本記事の入力依存の例題では、条件を指定して最良・最悪を区別します。問題文に指定がある場合は、それを優先し、勝手に平均や最悪へ置き換えないでください。

ifの中で二つの処理のどちらかを選ぶときも、実行される経路を分けます。O(n)の処理とO(n²)の処理が前後に必ず実行されるなら加算ですが、どちらか片方だけなら「両方の正確な回数を足す」ことにはなりません。最悪を問われたときは、実際に到達できる経路の中で最も大きくなる処理を調べます。

breakがあるループでは、終了の条件が必ず早い段階で成立するのか、最後まで成立しない入力もあるのかを確認しましょう。1回だけ抜けた具体例を見て、すべての入力でも同じ回数だと一般化するのは避けたいところです。

変数とループの中身を確認する

外側n回、内側m回のコードなら、合計はnm回です。mは別の配列の件数など、nと独立の入力サイズかもしれません。m＝nという条件がなければO(n²)へ変えず、O(nm)と表します。二つの配列を別々に1回ずつ走査するならO(n＋m)です。

たとえばn件の商品とm件の候補を総当たりで照合する場合、n＝4、m＝7なら比較は28回です。mがいつも固定3件なら3n回でO(n)ですが、mも入力に応じて増えるなら省略できません。nとmの関係を、問題文から確認する必要があります。

同じように、n回のループ内で「配列n件を全部確認する関数」を毎回呼ぶなら、外から見えるforが一重でもO(n²)になることがあります。関数名だけでは、その1回の仕事が一定量かどうか分かりません。定義、注記、処理対象の件数を読みましょう。

一定長の整数どうしの加算と、長さnの文字列全体を調べる処理は、同じ「1行」でも必要な仕事が違います。コードの行数を数えることと、処理量を数えることは別です。本記事の単純なcount加算には一定時間という前提を置いていますが、実際の問題で関数や複雑な演算が入ったときは、その前提を確かめてください。

時間計算量と空間計算量も分けます。n回繰り返しても、countとiなど少数の変数だけを追加で使うなら、追加の空間計算量はO(1)です。結果をn個の新しい配列へ保存するなら追加の空間はO(n)です。与えられた入力配列を含めた総メモリ量なのか、処理のために新しく使う領域なのかで表現が変わります。

n×nの表を全部作る場合は、要素を書き込む時間も保存する領域もO(n²)になり得ます。一方、同じ組合せを見ても保存せずcountだけ更新するなら、時間O(n²)、追加空間O(1)とできます。問題文に「時間」か「領域」かの指定があることを見落とさないようにしましょう。

練習問題で回数とオーダーを分ける

ここからは答えを見る前に、自分で「数える文の回数→一般式→オーダー」の順に書いてみてください。すべて独自の練習問題で、nは正の整数、countの加算は一定時間です。分からなければn＝4で変数の値を並べてから、n一般の式へ戻ります。

固定回数の内側ループ

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    for (j を 1 から 5 まで 1 ずつ増やす)
        count ← count + 1
    endfor
endfor

解答は5n回、O(n)です。n＝4なら20回になります。外側が入力とともに増えても、内側の5回は一定です。誤答O(n²)を選んだ場合は、ループの段数しか見ていない可能性があります。内側の上限が5で固定されている点を読み直しましょう。

終点を含まない三角形の反復

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    j ← 1
    while (j ＜ i)
        count ← count + 1
        j ← j + 1
    endwhile
endfor

解答は0＋1＋…＋(n−1)＝n(n−1)/2回、O(n²)です。n＝4なら0＋1＋2＋3＝6回です。j＜iなのでiと等しい値の回は実行しません。j≦iなら10回になるため、オーダーだけでなく不等号を含めて説明できるようにします。

毎回リセットされる倍増ループ

count ← 0
for (i を 1 から n まで 1 ずつ増やす)
    k ← 1
    while (k ≦ n)
        count ← count + 1
        k ← k × 2
    endwhile
endfor

解答はn×（log₂ nを切り捨てて1を加えた値）回、O(n log n)です。n＝4なら各回でk＝1、2、4の3回となり、合計12回です。kの初期化が外側の毎回に入っているため、倍増ループをnセット繰り返します。

初期化を外へ出すとどうなるか

直前の問題でk ← 1をforの前へ移した場合も考えてみましょう。最初のiでkはnより大きくなり、その後のiでは内側の本体が動きません。countの加算は全体で対数回なのでO(log n)です。ただし外側のforはn回残っています。管理処理も含めたコード全体の時間計算量はO(n)です。

この問題では、指定された文の回数とコード全体の時間計算量が違います。内側の加算が少ないから全体も同じ、と判断しない練習になります。どこまでを対象に求めるかを、設問の言葉に戻って確かめましょう。

練習の型	n＝4の加算回数	加算回数の増え方	全体の時間計算量
内側5回固定	20回	線形	O(n)
j＜iの三角形	6回	二次	O(n²)
倍増・毎回初期化	12回	線形×対数	O(n log n)
倍増・初期化は外	3回	対数	O(n)

答え合わせでは、正解の記号だけで終わらせず、間違えた原因を一つ決めます。上限を定数と読めなかった、不等号で1回ずれた、初期化の位置を飛ばした、設問の対象を取り違えた、というように分けると、次の問題で確認する場所がはっきりします。

基本情報の計算量とオーダーのまとめ

基本情報で計算量とオーダーを求めるときは、入力サイズを決め、数える処理を選び、変数が終了までどう進むかを読みます。単純なn回の反復はO(n)、毎回n回の内側反復はO(n²)、倍々に進む反復はO(log n)という型を、コードの条件と結び付けて理解しましょう。

• 逐次処理は回数を足し、入れ子は各回の内側の仕事を合計する
• 上限が外側の変数なら回数の列から式を作る
• 初期化の位置・更新式・終了条件・途中終了を確認する
• 正確な回数を聞かれたら係数・定数・端の1回も残す

とくに、二重ループという見た目に引っ張られず、固定回数、三角形、倍増、進み続ける添字を区別できることが目標です。n＝4で追った結果が、n＝8でどう増えるかまで説明できれば、式をオーダーへまとめる根拠も持てます。

代入や配列の添字を追う段階で止まった人は、まず擬似言語の読み方とトレース表の作り方で、1回の実行による値の変化を練習すると進めやすいです。回数は分かるのにオーダーだけ間違える人は、今回の回数の式から、定数と低次の項を落とす練習をしましょう。

解説を順に読みながら手を動かしたい人には、科目B向けの教材を使って例題と演習を往復する方法が向いています。すでに使っている参考書に十分な解説があるなら、まずその問題を解き直せばよく、追加購入は必須ではありません。新たに選ぶ場合は、解説の見本と版・対応範囲を確認してください。

教材を探す人は科目B専用参考書をAmazonで確認できます。このリンクはアフィリエイト広告です。購入先で内容を確認し、手順の解説が必要か、問題演習を増やしたいかに合わせて判断しましょう。

すぐに実際の問題で確かめたい人は、基本情報の過去問アプリで無料演習できます。科目A・科目Bに対応しているので、アルゴリズム分野の問題を選び、解答前に処理回数の根拠を書いてみてください。記号を選ぶだけでなく「どの文が何回動くか」を言葉にすることが、初めてのコードを読む練習になります。