算法学習ノート-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 つの場合を区別する必要はありません。同じコードブロックが異なる場合において、時間の複雑さに大きな差がある場合にのみ、これらの複雑さの表現方法を使用して区別します。

償却時間の複雑さ#

次に、例を挙げます：

// 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)です。」とのことです。読んでみて、すっきりしました！

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

例を使用して説明します。毎回の O (n) の挿入操作は、n-1 回の O (1) の挿入操作に続きます。したがって、時間のかかる操作を n-1 回の時間のかからない操作に均等に分散させることで、この一連の操作の均等な時間の複雑さは O (1) です。

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

一連の操作を行うためにデータ構造を使用する場合、ほとんどの場合、時間の複雑さは非常に低く、一部の場合のみ時間の複雑さが高くなる可能性があります。さらに、これらの操作は前後に連続性があります。一般的には、n-1 回の O (1) の挿入操作 (配列が満杯でない場合のデータの挿入) の後に、O (n) の操作 (配列が満杯の場合の配列の走査、クリア) が続きます。このような場合には、これらの高い時間の複雑さの操作の時間を他の低い時間の複雑さの操作に均等に分散することができる場合にのみ、均摊時間の複雑さの分析方法を適用することができます。そして、均摊時間の複雑さは通常、最良の場合の時間の複雑さと同じです。

均摊時間の複雑さは、特定の場合における平均時間の複雑さの一種です。

まとめ#

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

課題#

// グローバル変数、サイズが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 の場合が同じ確率で発生するため、加重平均の計算方法に基づいて、平均時間の複雑さは次のようになります：