【C++入門】時間計算量の求め方を実例で徹底解説！O(n)からO(n log n)まで

時間計算量（タイム・コンプレキシティ）とは、あるアルゴリズムが処理を完了するまでにかかる時間のことです。アルゴリズムの効率性を示す重要な指標であり、複数のアルゴリズムを比較・分析する際にも用いられます。一般的に、時間計算量を小さく抑えるほど、アルゴリズムはより効率的になります。

本記事では、C++のコードスニペットを題材に、代表的な時間計算量である O(1)、O(n)、O(n²)、O(log n)、O(n log n) を実際のコードから読み解く方法を、5つの例を通じて解説します。

例1：ループ変数が2ずつ増加する場合 → O(n)

次のコードの時間計算量を求めてみましょう。

for(i = 0; i < n; i++){
    cout << i << " ";
    i++;
}

ループの上限値は n ですが、ループ本体の中でも i がインクリメントされているため、実質的に i は1回の繰り返しごとに2ずつ増加します。その結果、ループが回る回数は約半分になり、処理時間も半分で済みます。したがって、時間計算量は O(n/2) となりますが、定数倍は無視できるため、これは O(n) と同等です。

例2：二重ループの場合 → O(n²)

次のコードの時間計算量を求めてみましょう。

for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
        cout << i << " ";
    }
}

外側のループと内側のループが、どちらも n 回ずつ実行されます。i の1つの値につき j は n 回ループするため、i が n 通りの値を取る間に、j のループは合計 n × n = n² 回実行されます。したがって、時間計算量は O(n²) です。

例3：値が毎回半分になるループ → O(log n)

次のコードの時間計算量を求めてみましょう。

int i = n;
while(i){
    cout << i << " ";
    i = i / 2;
}

このケースでは、反復ごとに i の値が前の値の半分になっていきます。したがって、i の値は n, n/2, n/4, n/8, …, 1 というように変化していきます。値が半減しながら1に達するまでに必要な反復回数は log₂n 回程度であるため、時間計算量は O(log n) となります。

例4：条件分岐のみの場合 → O(1)

次のコードの時間計算量を求めてみましょう。

if(i > j){
    j > 23 ? cout << j : cout << i;
}

このコードには2つの条件判断が含まれています。それぞれの条件判断の時間計算量は O(1) であり、2つ合計しても O(2) となります。定数倍は無視できるため、これは O(1)、すなわち定数時間と同等です。

例5：外側が線形・内側が対数の二重ループ → O(n log n)

次のコードの時間計算量を求めてみましょう。

for(i = 0; i < n; i++){
    for(j = 1; j < n; j = j * 2){
        cout << i << " ";
    }
}

内側のループは j が2倍ずつ増加するため log n 回実行され、外側のループは n 回実行されます。i の1つの値につき j は log n 回動作するため、i が n 通りの値を取る間に、内側のループは合計 n × log n 回実行されます。したがって、時間計算量は O(n log n) です。

まとめ：計算量パターンの一覧表

ビッグオー記法では定数倍や低次の項は無視されるため、「O(n/2)」や「O(2)」のような表記は「O(n)」「O(1)」に簡略化されます。ループ変数の増加パターン（1ずつ増えるか、2倍になるか）とループのネストの深さに注目すれば、多くのコードの時間計算量を直感的に見極められるようになります。ぜひ自分のコードでも試してみてください。