C++で学ぶ興味深い時間計算量の問題

時間計算量（Time Complexity）とは、アルゴリズムが平均的なケースで実行されるまでに必要となる時間として定義できます。

ここでは、基本的な関数の時間計算量を実際に見ていきながら、その求め方を解説します。

例1：内側のループが i ずつ増加する場合

void counter(int n){
    for(int i = 0; i < n; i++){
        for(int j = 1; j < n; j += i){
            cout << i << " " << j;
        }
        cout << endl;
    }
}

上記のメソッドでは、内側のループは各 i の値に対して n / i 回実行されます。つまり、最初の反復では約 n 回、最後の反復では 1 回実行されることになります。

これに基づくと、合計の時間計算量は次のように表せます。

(n/1 + n/2 + n/3 + … + n/n)
= n × (1/1 + 1/2 + 1/3 + … + 1/n)

ここで、(1/1 + 1/2 + 1/3 + … + 1/n) は調和級数と呼ばれるもので、その値は O(log n) に相当します。

したがって、このコード全体の時間計算量は O(n log n) となります。

例2：内側のループが log(i) 回実行される場合

void counter(int n){
    int i, j;
    for(int i = 1; i <= n; i++){
        for(j = 1; j <= log(i); j++){
            cout << i << " " << j;
        }
    }
}

この関数の合計計算量は、O(log 1) + O(log 2) + O(log 3) + … + O(log n) となります。これは対数の和をまとめて O(log n!) と表すことができます。

さらに、スターリングの近似によれば log n! は O(n log n) と近似できるため、実質的な計算量は O(n log n) であると考えることもできます。

まとめ

このように、ネストしたループの計算量を求める際には、単に「ループが二重だから O(n²)」と結論づけるのではなく、内側のループが実際に何回実行されるのかを数学的に分析することが重要です。調和級数や対数の和といった数列の性質を理解しておくと、より正確な計算量の評価ができるようになります。