算法学習ノート-02

最良、最悪、平均、償却時間の複雑さの浅い分析

最良、最悪時間の複雑さ#

以下のコードを例に挙げます：

// nは配列arrayの長さを表します
int find(int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
    for (; i < n; ++i) {
        if (array[i] == x) {
            pos = i;
            break;
        }
    }

    return pos;
}

このコードの時間の複雑さは $O (n)$ ですか？おそらく違います。

このような場合、コードの時間の複雑さは状況によって異なるため、以下のような時間の複雑さがあります：

最良の場合の時間の複雑さ：理想的な場合における、このコードの実行時間の複雑さ。この例では、非常に幸運で、array [0] でこの数を見つけることができれば、コードはここで停止します。この場合、このコードの時間の複雑さは $O (1)$ です。

最悪の場合の時間の複雑さ：最悪の場合における、このコードの実行時間の複雑さ。この例では、非常に不運で、array [n-1] で見つかるか、またはこの数が見つからない場合、コードは配列全体を完全に走査する必要があります。この場合、このコードの時間の複雑さは $O (n)$ です。

平均時間の複雑さ#

それでは、最良の場合の時間の複雑さと最悪の場合の時間の複雑さは、極端すぎるかもしれませんし、発生する確率も非常に低いため、このコードの時間の複雑さを客観的に表現することはできません。そのため、より良い平均的な場合の複雑さを表現するために、平均時間の複雑さの概念を導入する必要があります。

先ほどの例に戻ると、変数 x が配列内の位置には n+1 種類の場合があります：配列の [0]〜[n-1] の位置にある(n) または配列に存在しない(1)。各場合で、この数を見つけるために必要な要素の数を累積し、n+1 の場合で割ることで、この数を見つけるために必要な要素の数の平均値を得ることができます。つまり：

要素の数の平均値

したがって、時間の複雑さの大 O 表記法に基づいて、係数、定数、低次は無視できます。したがって、簡略化すると、平均時間の複雑さは $O (n)$ です。

3月18日、疑問があります。どのように簡略化するのですか？理解できません。難しいです。このような分数形式では、最高次の項を見るだけでいいのでしょうか？

3月19日、質問に答えます。どのように簡略化するのですか？LeetCodeでの説明によると、一般的な方法を応用して、n(n+3) / 2(n+1)を展開すると(n^2+3n) / (2n+2)になります。定数は無視できるため、(n^2+3n) / (2n) = (n+3) / 2に簡略化できます。したがって、簡略化された平均時間の複雑さはO(n)です！！！

したがって、この結論にはいくつかの小さな問題があります。配列内の変数 x の位置の n+1 の場合、それぞれの発生確率は同じではありません。

まず、配列内に変数 x があるかどうかを考えます。簡略化するために、配列内にあると配列内にないの確率はどちらも $1 \over 2$ とします。さらに、配列内に出現する位置 [0]〜[n-1] の確率も同じで、$1 \over n$ です。したがって、確率の乗法法則に基づいて、要素が [0]〜[n-1] のどの位置に現れるかの確率は $1 \over 2n$ です。

したがって、この場合、確率を考慮した平均複雑度の計算プロセスは次のようになります：

確率を考慮した平均時間の複雑さの計算プロセス

この値は確率論の加重平均値または期待値と呼ばれるものであり、平均時間の複雑度は加重平均時間の複雑度または期待時間の複雑度と呼ばれるべきです。

最後に、このコードの加重平均時間の複雑度は依然として $O (n)$ です。

実際、ほとんどの場合では、最良、最悪、平均の時間の複雑度の 3 つの場合を区別する必要はありません。同じコードブロックが異なる場合において、時間の複雑度に大きな差がある場合にのみ、これらの 3 つの複雑度表現法を使用して区別します。

償却時間の複雑度#

次に、例を挙げます：

// arrayは長さnの配列です
// コード内のarray.lengthはnです
int[] array = new int[n];
int count = 0;

void insert(int val) {
    if (count == array.length) {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
        }
        count = 1;//配列をクリア
        array[0] = sum;
     }

    array[count] = val;
        ++count;
 }

このコードのロジックは次のとおりです：まず、この関数の基本的な機能は、整数配列に値を挿入することです。配列がいっぱいになった場合、つまり count == array.length の場合、配列を走査して合計を求め、配列をクリアし、合計値を配列の [0] の位置に入れます。その後、挿入する値を [count] の位置に挿入します。配列がいっぱいでない場合、つまり count != array.length の場合、値を配列に挿入します。

注意：この場合、配列をクリアする操作はcountを1に設定します。読み書き可能なストレージの場合、使用者はそれが空であると見なします。もし、空がすべて0または特定の値になると定義するなら、それも可能です！使用者は新しい値を保存するだけに関心を持つべきです。

このコードでは、以下の時間の複雑さの分析方法を適用します。

最良の場合、配列に空きスペースがある場合 (配列がいっぱいでない場合)、値を配列 [count] の位置に挿入するだけです。** 最良の場合の時間の複雑さは $O (1)$** です。
最悪の場合、配列に空きスペースがない場合 (配列がいっぱいの場合)、配列を走査して合計を求め、値を挿入する必要があります。** 最悪の場合の時間の複雑さは $O (n)$** です。
平均時間の複雑さは、確率論の方法を使用して分析することができます。配列の長さが n であると仮定すると、挿入位置によって n 種類の場合があります。それぞれの場合の時間の複雑さは $O (1)$ です。また、配列がいっぱいの場合も 1 つの場合があり、その場合の時間の複雑さは $O (n)$ です。さらに、これらの n+1 の場合が同じ確率で発生するため、加重平均の計算方法に基づいて、平均時間の複雑さは次のようになります：

3月18日、疑問があります。左側は2n / n+1ですが、それでもO(n)としてもいいのではありませんか？本当に理解できません...

3月19日、質問に答えます。どのように簡略化するのですか？LeetCodeでの説明によると、「2n/(n+1)の上下の数量はnであり、2n/n = 2であり、時間の複雑度は定数であるため、O(1)です。」とのことです。読んだ後、すっきりしました。

実際、このような特殊なシナリオの複雑度分析には、より簡単な分析方法である償却分析法を適用します。償却分析法によって得られる時間の複雑さは均等時間の複雑さと呼ばれます。

例を使用して説明します。各 n 回の O (1) 操作の後には必ず 1 回の O (n) 操作が続きます。タイミングがあり、均等になるため、時間のかかる操作を次の n-1 回の時間のかからない操作に均等に分散させることで、この一連の操作の均等時間の複雑さは O (1) です。

平均時間の複雑さと均摊時間の複雑さの適用範囲#

一連の操作を行うためにデータ構造を使用する場合、ほとんどの場合、時間の複雑さは非常に低く、一部の場合のみ時間の複雑さが高くなります。さらに、これらの操作は前後に連続性があり、均等に分散される場合、均摊時間の複雑さを適用することができます。そして、均摊時間の複雑さの適用範囲では、一般に均摊時間の複雑さは最良の場合の時間の複雑さと同じです。

均摊時間の複雑さは、特殊な平均時間の複雑さです。

内容のまとめ#

いくつかの複雑度分析に関連する概念があります。最良の場合の時間の複雑さ、最悪の場合の時間の複雑さ、平均時間の複雑さ、均摊時間の複雑さです。これらの概念を導入したことで、コードの実行効率をより包括的に表現することができるようになりました。

課題の考察#

// グローバル変数、サイズが10の配列array、長さlen、インデックスi。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 配列に要素を追加する
void add(int element) {
    if (i >= len) { // 配列の空きスペースがない
        // サイズが2倍の新しい配列空間を再度要求する
        int new_array[] = new int[len*2];
        // 元のarray配列のデータをnew_arrayに順番にコピーする
        for (int j = 0; j < len; ++j) {
            new_array[j] = array[j];
        }
        // new_arrayをarrayにコピーし、arrayのサイズは2倍になる
        array = new_array;
        len = 2 * len;
    }
    // elementをiの位置に入れ、iをインクリメントする
    array[i] = element;
    ++i;
}

このコードでは、配列に要素を追加します。配列が満杯でない場合、つまり i >= len の場合、要素を配列に挿入します。配列が満杯の場合、つまり i < len の場合、新しい配列空間を要求し、元の配列のデータを新しい配列にコピーし、新しい配列を元の配列に置き換えます。

このコードでは、以下の時間の複雑さの分析方法を適用します。

最良の場合、配列に空きスペースがある場合 (配列が満杯でない場合)、要素を配列 [i] の位置に挿入するだけです。** 最良の場合の時間の複雑さは $O (1)$** です。
最悪の場合、配列に空きスペースがない場合 (配列が満杯の場合)、配列を走査して合計を求め、配列をクリアする必要があります。** 最悪の場合の時間の複雑さは $O (n)$** です。
平均時間の複雑さは、確率論の方法を使用して分析することができます。配列の長さが n であると仮定すると、挿入位置によって n 種類の場合があります。それぞれの場合の時間の複雑さは $O (1)$ です。また、配列が満杯の場合も 1 つの場合があり、その場合の時間の複雑さは $O (n)$ です。さらに、これらの n+1 の場合が同じ確率で発生するため、加重平均の計算方法に基づいて、平均時間の複雑さは次のようになります：

実際、この特殊なシナリオの複雑度分析では、より簡単な分析方法である償却分析法を適用することができます。償却分析法によって得られる時間の複雑さは均摊時間の複雑さと呼ばれます。