科目Bの計算量問題の解き方｜ループの形からオーダーを判断する

この行が何回実行されるか、と聞かれると急に自信がなくなる。

二重ループの問題で、選択肢に n の2乗と n(n-1)/2 が並んでいて迷ったことはありませんか？

計算量の問題は、数学の知識を問われているように見えます。けれど実際に必要なのは、ループが何回回るかを落ち着いて数える手順だけです。

迷ってしまう原因の多くは、公式を思い出そうとすることにあります。公式より先に、小さな数で実際に数えてみる。それだけで答えはかなり絞れます。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務では、テスト環境では一瞬で終わる処理が、本番の大量データで何十分もかかる場面に何度も出会ってきました。

原因を調べると、たいていはループの中に隠れたもう一つのループです。この記事では、そうした形をコードから見抜いて、科目Bの設問に答える手順をお伝えします。

科目B全体でどんな問題が出るのかを先に確かめたい人は、親記事から読むと位置づけがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

この設問は何を聞いているのか¶

最初に、計算量の問題で何が問われているのかを整理しましょう。聞き方を知っておくと、読むべき場所がすぐに決まります。

科目Bで計算量が絡む設問は、オーダーという言葉が出てこないこともあります。多いのは、ある行が何回実行されるか、あるいは n が2倍になったら処理回数が何倍になるか、という形です。

聞き方で分けると、おおむね次の3つになります。どれも中身は、ループの回数を数えることに行き着きます。

実行回数を問われたら、正確な式が必要です。オーダーを問われたら、細かい定数は気にせず形だけを見れば足ります。

正確な回数とオーダーは別の答え¶

ここで混同しやすいのが、正確な回数とオーダーの違いです。たとえば n(n-1)/2 回の処理は、正確な回数としては n² とは違います。

ところがオーダーで表すと、どちらも O(n²) になります。設問がどちらを聞いているのかを読み違えると、選択肢の中で正解が2つあるように見えてしまいます。

問題文の最後の一文を、必ず先に読んでください。回数を聞いているのか、伸び方を聞いているのかで、答えの粒度が決まります。

計算量やオーダーという考え方そのものに不安がある人は、こちらの記事で基本を先に押さえておくと読みやすくなります。

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

まず目を付ける場所¶

コードを開いたら、1行目から順に意味を追う必要はありません。計算量の問題では、処理の中身よりも繰返しの形のほうが大事だからです。

見るのは次の3か所です。この順に確認すると、どのくらいの回数になるかの見当がすぐにつきます。

1つ目は、インデントを指でなぞるだけで分かります。問われている行が endfor の何段内側にあるかが、回数の骨組みになります。

内側のループの開始位置に注目する¶

いちばん差が出るのは2つ目です。内側のループが 1 から n までなら、外側が何回目であっても毎回 n 回回ります。

一方で、内側が i + 1 から n までのように外側の変数を使っていたら話が変わります。外側が進むほど、内側の回数が1回ずつ減っていくからです。

この1点を見落とすと、n² と n(n-1)/2 を取り違えます。開始位置に i が含まれていないかを、まず確かめてください。

増え方が1ずつでなければ log を疑う¶

3つ目の増え方も見逃せません。変数が 1 ずつではなく、2倍になったり半分になったりしていたら、回数は log になります。

たとえば n が 16 なら、半分にしていく処理は 16、8、4、2、1 と数回で終わります。while 文で書かれることが多いので、条件式と更新の行をセットで見るのがコツです。

二重ループそのものの読み方に慣れていない人は、文法を扱ったこちらの記事で先に固めておくと安心です。

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

例題：組み合わせを数える処理の実行回数¶

ここからは例題で実際に追ってみます。IPAの公開問題そのものではなく、科目Bでよく見かける形をもとに作った類題です。

処理の内容は、配列の中から、足すと目標の値になる2つの要素の組がいくつあるかを数えるものです。同じ組を二重に数えないよう、内側のループを工夫しています。

○整数型: countPairs(整数型の配列: data, 整数型: target)
  整数型: n, i, j, count
  n ← data の要素数
  count ← 0
  for (i を 1 から n - 1 まで 1 ずつ増やす)
    for (j を i + 1 から n まで 1 ずつ増やす)
      if (data[i] + data[j] が target と等しい)   /* α */
        count ← count + 1
      endif
    endfor
  endfor
  return count

設問は、α の行が何回実行されるかを n を使って表せ、というものだとします。先ほどの3か所を当てはめてみましょう。

α は二重ループの内側にあります。外側は 1 から n - 1 まで、内側は i + 1 から n までで、内側の開始位置に i が入っています。

変数はどちらも1ずつ増えます。ここまで見れば、回数は n² より少なくなりそうだと見当がつきます。

トレース表で回数を数える¶

では、n が 4 のときに実際に数えてみましょう。表の列は、外側の i、そのときの内側の j の範囲、そして α が実行される回数です。

n が 4 のとき、α は合計6回実行されます。外側が進むたびに、内側の回数が 3、2、1 と1つずつ減っているのが分かります。

この 3 + 2 + 1 という形は、1 から n - 1 までの和です。和の公式に当てはめると n(n-1)/2 になり、n が 4 なら 4 × 3 ÷ 2 で 6 です。

式は小さな n を2つ当てて確かめる¶

公式を覚えていなくても心配はいりません。選択肢の式に n = 4 を入れて、6 になるものを探せば十分です。

ただ、1つの n だけでは偶然一致する式が残ることがあります。念のため n = 3 でも数えておくと安心です。

n が 3 なら、i が 1 のとき2回、i が 2 のとき1回で、合計3回になります。n(n-1)/2 に当てはめると 3 × 2 ÷ 2 で 3 なので、こちらも一致します。

2つの n で一致すれば、ほぼ間違いありません。表を書く時間は1分もかからないので、式を疑うより数えたほうが早いのです。

トレース表の書き方そのものをもっと詳しく知りたい人は、こちらの記事が参考になります。

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

オーダーを聞かれたら形だけで答える¶

同じコードで、オーダーを問われた場合も考えてみましょう。n(n-1)/2 を展開すると、n² を2で割った項と、n を2で割った項になります。

オーダーでは、いちばん伸びの大きい項だけを残し、係数も外します。すると残るのは n² なので、答えは O(n²) です。

つまり、正確な回数は n² の約半分でも、伸び方としては n² と同じ仲間です。n が2倍になれば、処理回数はおよそ4倍になります。

半分ずつ減らすループも一度数えておく¶

もう一つ、log になる形も小さな例で確かめておきましょう。次のコードは、n を半分にしながら何回割れるかを数える処理です。

○整数型: halvingCount(整数型: n)
  整数型: m, count
  m ← n
  count ← 0
  while (m が 1 より大きい)
    m ← m ÷ 2 の商
    count ← count + 1   /* β */
  endwhile
  return count

n が 16 なら、m は 16、8、4、2、1 と変わり、β は4回実行されます。n が 32 に倍増しても、回数は5回と1回しか増えません。

これが O(log n) の性格です。二分探索が速いと言われるのも、調べる範囲を毎回半分に絞っているからです。

間違いやすい選択肢の見分け方¶

計算量の問題の選択肢は、正解とよく似た式がいくつも並びます。どこが違うのかを見れば、作問者がどんな読み間違いを狙っているかが分かります。

例題の α の実行回数について、並びそうな選択肢を表にしてみました。n = 4 のときの値も添えておきます。

どの誤りも、ループの開始位置か終了位置の読み違いから生まれています。処理の中身ではなく、範囲の端で差がつくのです。

表のように n = 4 の値を並べると、選択肢の違いがはっきり見えます。式のままで比べるより、数に直したほうが迷いません。

1回ずれる選択肢は境界を見る¶

n(n-1)/2 と n(n+1)/2 のように、1だけずれた選択肢もよく出ます。この違いは、外側のループが n - 1 で止まるか n まで回るか、内側が i + 1 から始まるか i から始まるかで決まります。

こうした1回のずれは、範囲の境界を指で押さえれば防げます。for の行の数字を、一つずつ声に出して確認するくらいでちょうどいいです。

ループの回数や境界の数え方に自信がない人は、繰返しの問題を扱ったこちらの記事もあわせてどうぞ。

【関連記事】科目Bの繰返し問題が解けない人へ｜ループ回数を追うコツ

実務でも回数の見積もりが効く¶

実務でも、この見積もりはそのまま役に立ちます。私が以前担当した画面では、会員一覧のすべての組を突き合わせる処理があり、件数が増えるにつれて表示が目に見えて遅くなっていきました。

調べると、例題と同じ二重ループでした。件数が10倍になると処理は約100倍になるので、少し増えただけで体感が大きく変わったのです。

試験でループの形から回数を読む練習は、現場でコードの危うさに気づく力にそのままつながります。点数のためだけでなく、長く使える力だと思って取り組んでみてください。

シミュレーターで動かして確かめる¶

ここまで紙の上で数えてきましたが、最後は実際に動かしてみるのがいちばん確実です。自分で数えた回数と、実際の動きが一致するかを確かめられるからです。

Giji Academyの擬似言語シミュレーターでは、擬似言語のコードを1行ずつ動かし、変数の値が変わる様子を見ることができます。二重ループのように i と j が同時に動く処理こそ、目で見ると理解が早まります。

カウンタを足して回数を数えさせる¶

おすすめの確かめ方は、問われている行のすぐ下に、回数を数えるだけの変数を足すことです。今回の例題なら、α の行で別の変数を1増やしておき、最後にその値を見ます。

n を 3、4、5 と変えて動かし、3、6、10 と値が出るかを確認してみてください。n が 5 のときは、n(n-1)/2 に当てはめると 10 になるはずです。

さらに、内側の開始位置を i + 1 から 1 に変えたらどうなるかも試してみましょう。先ほどの選択肢の表と同じ n² の結果が出れば、ひっかけの仕組みまで自分のものになっています。

自分で手を動かして確かめたい人は、Giji Academyの擬似言語シミュレーターから繰返しや配列の講座を選んでみてください。読むだけの勉強より、ずっと記憶に残ります。

まとめ¶

科目Bの計算量問題は、公式を覚えているかではなく、ループの回数を落ち着いて数えられるかで決まります。実行回数を聞かれているのか、オーダーを聞かれているのかを、まず問題文の最後で確かめましょう。

コードを開いたら、問われている行の位置、各ループの開始と終了、変数の増え方の3か所に目を付けます。特に内側のループの開始位置に外側の変数が入っていないかが、答えを分ける大事なポイントでした。

例題では、n が 4 と 3 のときに実際に数え、n(n-1)/2 という式を確かめました。オーダーで答えるなら、係数と小さな項を外して O(n²) になります。

紛らわしい選択肢の違いは、ほとんどがループの端の読み違いです。式を数に直して並べれば、どれが正解かは自然に見えてきます。

最初は表を書くのに時間がかかっても大丈夫です。何問か数えるうちに、ループの形を見ただけで回数の見当がつくようになります。