アルゴリズムの複雑度分析(下)

2534 ワード

前の文章のアルゴリズムの複雑度分析において、複雑度の大きいO表示法といくつかの分析原則を述べました.この文章は他のいくつかの複雑さを説明します.最良の場合、時間複雑度、最悪の場合、時間複雑度、平均時間複雑度(average case case time complexity)、平均時間複雑度(average case case case case time complexity)割り勘時間の複雑さ.
最悪の場合、時間の複雑さ
その名の通り、この2つの時間の複雑さは特殊な場合の時間の複雑さを意味します.私たちは次の例を見ます.

// 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;
}

このコードで実現される機能は、配列arrayで変数xが最初に出現した位置を探します.見つけられなかったら-1を返します.位置下付きに戻ります.
前の文章の方法では、このコードの複雑さは明らかに解析できません.なぜなら、場合によっては時間の複雑さが違ってくるからです.配列の最初の要素がxである場合、時間の複雑さはO(1)である.最後の要素がxである場合、時間複雑度はO(n)である.
コードの場合によって時間の複雑さを表すために、時間の複雑さ、最悪の場合の複雑さ、平均状況の時間複雑さの3つの概念を導入する必要があります.
その中で、最適な場合の時間複雑さは、理想的な状況でコードを実行する時間の複雑さであり、その時間は最短である.最悪の場合、時間の複雑さは最悪の場合、コードを実行する時間の複雑さであり、その時間は最長である.
平均状況時間複雑度
最も良くて、最も悪い時間の複雑さの反応のは極端な条件の下の複雑さで、発生の確率は大きくなくて、平均レベルを代表することができません.平均の場合のアルゴリズムの複雑さをより良く表現するためには、平均時間の複雑さを導入する必要がある.
前のfind関数を使用し続けると、変数xが配列arry内にある確率とない確率がそれぞれ1/2と仮定されます.配列内に存在する場合、位置毎の確率は均等で、1/nとなります.平均時間の複雑さは次のように計算されます.((1 + 2 + ... + n) / n + n) / 2 = (3n + 1) / 4この値は確率論の加重平均であり、期待値ともいう.したがって、平均時間複雑度は、加重平均時間複雑度または期待時間複雑度とも呼ばれる.find関数の平均時間複雑度はO(n)であることがわかる.
ほとんどの場合、最高、最悪、平均状況を区別する必要はなく、複雑さだけで需要を満たすことができます.同じブロックのコードが異なる場合にのみ、時間の複雑さには、桁の違いがある場合にのみ、この3つの複雑さを考慮する必要があります.
時間割りの複雑さ
上記から分かるように、平均時間の複雑さは特別な時にしか使えません.時間割りの複雑さの応用シーンはそれよりもっと特殊です.割り勘時間の複雑さとは、ほとんどの場合、時間の複雑さが低く、場合によっては時間の複雑さが比較的高い場合のみであり、これらの動作の間に前後一貫したタイミング関係が存在する場合、時間の複雑度が高い操作を時間と時間の複雑度が低い操作に均等に割り当てることができるというものです.この分析方法を屋台分析法といい、得られた複雑さを割り勘時間の複雑さといいます.
また、均匀時間の複雑さを分析できる場合、均匀時間の複雑さは最良の場合の時間複雑度に等しい.
たとえば:

int[] array = new int(n);
int count = 0;

void addLast (int val) {
    if (count == array.length) {
        int[] newArray = new int(2 * n);
        for (int i = 0; i < 2 * n; i++) {
            newArray[i] = array[i];
        }
        newArray[count] = val;
        array = newArray;
    } else {
        array[count] = val
    }
    count++;
}

このコードが実装されている機能は、配列の末尾に要素を追加します.配列が満杯でない場合は、要素を直接後ろに挿入します.配列がいっぱいである場合、すなわちcount == array.lengthは、配列を二倍に拡大し、要素を挿入する.
例えば、配列長がnの場合、最初のn回の呼び出しのaddLast()の複雑さはすべてO(1)である.n＋1回目はまずn回の要素移動操作を行い、その後1回の挿入操作を行い、複雑度はO(n)となります.また、O(1)の複雑度の操作とO(n)の複雑度の動作の出現頻度は規則的であり、n回のO(1)操作ごとにO(n)の動作が続くことが分かりやすい.
そうすると、O(n)操作の複雑さをO(1)操作毎に均等に割り出すことができ、この操作は(n + n * 1) / (n + 1) = 2n / (n + 1)回の操作が必要なので、均等に複雑度をO(1)とする.
この文章は初めてWeChat公衆号より『コードは書き終わりました.』

アルゴリズム1

毎日計算方を書いて、迷宮城.