はじめに: 計算量は「データが増えたときの伸び方」を見る考え方
線形探索、二分探索、スタック、キューを学ぶと、「同じような処理でも、データが増えたときの重さが違う」という感覚が出てきます。
たとえば線形探索では、100件なら最大100回、1000件なら最大1000回のように、探す回数がデータ件数に比例して増えます。一方、二分探索では探索範囲を半分ずつ狭めるため、データが増えても比較回数はゆるやかに増えるだけです。
このように、入力データが増えたときに処理の手間がどう増えるかを表す考え方が「計算量」です。基本情報技術者試験で出てくる O(n) や O(log n) は、暗記用の記号ではなく、コードの重さを「伸び方」で読むための道具です。
Webアプリでも、一覧の絞り込み、APIから受け取ったデータの検索、配列の並べ替えなどで計算量は関係します。データが少ないうちは問題なく動く処理でも、件数が増えると急に重く感じることがあります。
計算量は、入力データが増えたときに処理の手間がどう増えるかを見る考え方です。
計算量とは何か
計算量とは、ある処理を実行するために必要な手間を表す考え方です。ここでいう手間とは、実際に何秒かかったかではなく、比較、代入、繰り返しのような処理がどれくらい増えるかをざっくり見るものです。
実行時間は、PCの性能、ブラウザ、JavaScriptエンジン、同時に動いている別の処理などに左右されます。そこで計算量では、入力データの件数を n と置き、「nが増えたときに処理回数がどう増えるか」を考えます。
配列を先頭から最後まで確認する処理なら、データが n 件あると最大で n 回確認します。一方、二分探索のように探索範囲を半分ずつ減らせる処理では、データが2倍になっても確認回数は1回増える程度です。
試験で計算量が問われるのは、この「伸び方」を読み取る力が重要だからです。コードを丸暗記するのではなく、どの処理が何回くり返されるのかを見ることが第一歩です。
計算量では、入力データの件数を n として、処理回数の増え方を考えます。
オーダ記法の基本: O(1), O(n), O(log n), O(n^2)
オーダ記法は、データ量が増えたときの大まかな伸び方を表す記法です。
O(1) は、データ件数にほぼ関係なく一定の手間で終わる処理です。配列の特定位置にある値を取り出す処理や、スタックの末尾に要素を追加する処理が例です。
O(n) は、データ件数に比例して処理回数が増える処理です。配列を先頭から最後まで順番に確認する線形探索が代表例です。
O(log n) は、データを半分ずつ減らす処理で出てきます。二分探索のように、1回の比較で探索範囲を半分にできる処理です。
O(n^2) は、二重ループなどで出てくる、処理回数が大きく増えやすいパターンです。外側のループが n 回、内側のループも n 回動くと、全体は n * n に近い増え方になります。
O(1)、O(n)、O(log n)、O(n^2) は、処理回数の細かな値ではなく増え方の型を表します。
JavaScriptで O(n) を見る: 線形探索の処理回数
O(n) の例として、配列の先頭から順番に値を探す線形探索を見てみます。
function linearSearch(items, target) {
let count = 0;
for (let i = 0; i < items.length; i++) {
count++;
if (items[i] === target) {
return { index: i, count };
}
}
return { index: -1, count };
}この関数では、配列 items の要素を先頭から1つずつ確認しています。count は比較した回数です。目的の値が見つかればそこで終了し、見つからなければ最後まで確認します。
配列が5件なら最大5回、1000件なら最大1000回、10000件なら最大10000回比較します。このように、データ件数が増えるほど処理回数も同じように増える処理を O(n) と表します。
線形探索は仕組みが単純で分かりやすい一方、データが大きくなるほど処理回数もまっすぐ増えていくアルゴリズムです。
線形探索は、最大の比較回数がデータ件数に比例します。
JavaScriptで O(log n) を見る: 二分探索の処理回数
O(log n) の例として、二分探索を見てみます。二分探索は、ソート済みの配列に対して使える探索方法です。中央の値を確認し、目的の値が左側にあるのか右側にあるのかを判断して、探索範囲を半分ずつ狭めます。
function binarySearch(items, target) {
let left = 0;
let right = items.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (items[middle] === target) return middle;
if (items[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}線形探索では先頭から順番に1つずつ確認します。二分探索では、1回比較するたびに探索対象が半分に減ります。8件なら、8件、4件、2件、1件のように範囲が小さくなります。16件になっても、16件、8件、4件、2件、1件という流れなので、確認回数は大きく増えません。
ただし、二分探索は配列が昇順や降順に並んでいることが前提です。ソートされていない配列では、中央を見ても左右どちらに目的の値があるか判断できません。
二分探索は、1回比較するたびに探索範囲を半分に減らすため O(log n) になります。
O(1) とデータ構造: スタック・キューの操作を例にする
O(1) は、データ件数が増えても処理の手間がほぼ一定と考えられる処理です。操作する場所が決まっている処理をイメージすると分かりやすくなります。
スタックは「後に入れたものを先に取り出す」データ構造です。JavaScriptの配列で考えると、末尾に要素を追加する push() と、末尾から要素を取り出す pop() が対応します。
const stack = [];
stack.push("A");
stack.push("B");
console.log(stack.pop()); // Bこの例では、最後に追加した "B" を取り出しています。配列の末尾だけを操作しているため、基本的にはデータ件数が増えても一定時間で扱える操作、つまり O(1) と見なせます。
キューは「先に入れたものを先に取り出す」データ構造です。ただし、JavaScriptの配列で shift() を使うと、残りの要素を前に詰める必要があるため、実装上はデータ件数の影響を受ける場合があります。
試験上のデータ構造と、JavaScript配列での実装コストは分けて考える必要があります。
計算量を見るときの注意点
計算量は便利ですが、O(n) や O(log n) だけを見ればすべて分かるわけではありません。あくまで、データが増えたときの大まかな伸び方を見るための道具です。
たとえば、ある処理が n 回、別の処理が 2n 回実行されるとしても、どちらも大きく見れば O(n) と表します。実際の速度には差が出ることがありますが、計算量では「比例して増える」という伸び方を重視します。
また、最良の場合、平均の場合、最悪の場合で処理回数が変わることもあります。線形探索なら、探す値が先頭にあれば1回で見つかります。しかし、最後にある場合や見つからない場合は、配列全体を確認します。
JavaScriptでは、map()、filter()、find() のような便利なメソッドにも注意が必要です。短く書けるので軽く見えますが、多くの場合は配列の要素を順番にたどっています。
コードの行数ではなく、データ件数に応じて何回くり返されるかを見ることが大切です。
試験ではどう問われるか
基本情報技術者試験で計算量を考えるときは、「どの処理が何回くり返されるか」を見るのが基本です。難しそうなコードでも、くり返しの構造を追うと判断しやすくなります。
配列を先頭から最後まで1回だけたどる処理であれば、O(n) と考えます。ループの中にさらにループがある場合は、O(n^2) を疑います。二分探索のように、1回の処理で対象範囲を半分にできる場合は O(log n) を疑います。
問題文に「整列済み」「中央の値と比較する」「探索範囲を半分にする」といった要素が出てきたら、線形探索とは違う伸び方をしていると考えます。
「全件を見る」「半分に減らす」「二重にくり返す」を見分けると、代表的な計算量を判断しやすくなります。
実務ではどう使われるか
実務で計算量を意識する場面は身近にあります。JavaScriptでは、画面に表示する一覧データを検索したり、絞り込んだり、並べ替えたりする処理で計算量が関係します。
たとえば、ユーザー一覧をブラウザ側で受け取り、入力されたキーワードに一致するユーザーを filter() で探す処理を考えます。100件程度なら問題なく動いても、10000件、100000件と増えると、入力のたびに全件を確認する処理が重く感じられることがあります。
このとき、「入力のたびに O(n) の処理をしているのではないか」と見られると、原因を探しやすくなります。絞り込みの中で別の配列を毎回検索していれば、気づかないうちに O(n^2) に近い処理になっているかもしれません。
Webアプリでは、すべてのデータをフロントエンドに渡してからJavaScriptで探すより、APIやデータベース側で必要な条件に絞り込むほうが自然な場合もあります。
計算量は、データが増えたときに問題になりそうな場所を見つけるための道具です。
まとめ: 計算量はコードの伸び方を読むための道具
計算量は、処理時間を正確に予測するためのものではありません。入力データが増えたときに、処理の手間がどのように伸びるかを読むための考え方です。
O(1) は一定、O(n) は比例、O(log n) は半分ずつ減る処理、O(n^2) は二重ループのように大きく増えやすい処理です。
基本情報技術者試験では、コードや説明文を読んで処理回数の増え方を判断する力が問われます。実務では、一覧検索、配列の絞り込み、APIから取得したデータの扱いなどで、同じ考え方が役に立ちます。
まずは、コードを見たときに「全件を見るのか」「半分に減らせるのか」「二重にくり返していないか」を考えるところから始めてみましょう。計算量は、暗記する記号ではなく、コードの伸び方を読むための道具です。
計算量は、暗記する記号ではなく、コードの伸び方を読むための道具です。
コメント