algorithm
Big-O表記法

備考

シンプルなループ

次の関数は、配列内の最大要素を見つけます。

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

入力サイズは配列のサイズです。これをコードでlenと呼びます。

操作を数えましょう。

int max = INT_MIN;
size_t i = 0;

これらの2つの割り当ては1回だけ実行されるため、2つの操作です。ループされる操作は次のとおりです。

if (max < array[i])
i++;
max = array[i]

ループには3つの演算があり、ループはn回実行されるので、既存の2つの演算に3nを足して3n + 2を得る。したがって、私たちの関数は3n + 2演算を行い、最大値（複雑さは3n + 2 ）を求めます。これは、最も急成長する項がnの因数である多項式なので、O（n）です。

あなたはおそらく、「操作」があまりよく定義されていないことに気づいたでしょう。例えば、私は、 if (max < array[i])が1つの演算であったが、アーキテクチャに応じて、このステートメントを例えば3つの命令、すなわち1つのメモリ読取り、1つの比較および1つの分岐でコンパイルすることができると述べた。私はまた、たとえメモリ操作が他のものより遅くても、すべての操作を同じと見なしました。そのパフォーマンスは、キャッシュ効果などによって大きく変わります。私はまた、リターンステートメント、フレームが関数などのために作成されるという事実を完全に無視しました。結局のところ、計算をどのように選択するかによって、 n因子と定数の結果はO（n）になります。複雑さは、アルゴリズムが入力のサイズにどのように比例するかを示しますが、パフォーマンスの唯一の側面ではありません。

ネストループ

次の関数は、各要素を取得して配列に重複があるかどうかをチェックし、配列全体を繰り返してその要素がそこにあるかどうかを調べます

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

内部ループは、各繰り返しにおいて、 nで一定である多数の演算を実行する。外側のループもいくつかの一定の操作を行い、内側のループをn回実行します。外部ループ自体はn回実行されます。したがって、内側ループ内の演算はn^2回実行され、外側ループの演算はn回実行され、 iへの代入は1回実行されます。したがって、複雑さはan^2 + bn + cようなものになり、最も高い項はn^2 、O表記はO(n^2)です。

気づいたことがあるかもしれませんが、同じ比較を何回も繰り返さないようにすることでアルゴリズムを改善することができます。前のすべての要素は、すでにインデックスi + 1配列要素を含むすべての配列要素に対してチェックされているため、内部ループのi + 1から開始できます。これにより、 i == jチェックを削除することができます。

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

明らかに、この2番目のバージョンは操作が少なく、効率的です。それはBig-O記法にどのように変換されますか？さて、内側ループ本体は、 1 + 2 + ... + n - 1 = n(n-1)/2回実行されます。これはまだ 2次の多項式なので、依然としてO(n^2)です。私たちが行っている操作の数を2で割ったので、複雑さをはっきりと下げましたが、Big-Oで定義されているのと同じ複雑さのクラスです。複雑さをより低いクラスに下げるためには、操作の数をn 無限になるようなものに分割する必要があります。

O（log n）の例

前書き

次の問題を考えてみましょう。

Lは、 [-5, -2, -1, 0, 1, 2, 4] （ここではnは7の値）など、 n n符号付き整数（ nは十分に大きい）を含むソートされたリストです。 Lが整数0を含むことがわかっている場合、どのようにしてインデックス0を見つけることができますか？

ナイーブアプローチ

最初に気になるのは、0が見つかるまですべてのインデックスを読み取ることです。最悪の場合、操作の数はnなので、複雑さはO（n）です。

これはn小さな値に対してうまく動作しますが、より効率的な方法がありますか？

二分法

以下のアルゴリズム（Python3）を考えてみましょう：

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

aとbは、その間に0が見つかるインデックスです。私たちはループに入るたびに、我々は間のインデックスを使用し、 a bと検索するエリアを絞り込むためにそれを使用します。

最悪の場合、 aとbが等しくなるまで待たなければなりません。しかし、どれくらいの操作がかかるのでしょうか？ N、我々はループに入るたびにので、我々は、距離分裂しないとa b約2で。むしろ、複雑さはO（log n）である。

説明

注： "log"と書くと、バイナリ対数、つまりlog base 2（ "log_2"と書かれます）を意味します。 O（log_2 n）= O（log n）（あなたが計算することができる）として、 "log_2"の代わりに "log"を使用します。

xを操作の数としましょう：1 = n /（2 ^ x）を知っています。

したがって、2 ^ x = n、x = log n

結論

連続的な分割（2つまたは任意の数で）に直面するとき、複雑さは対数であることを忘れないでください。

O（log n）型のアルゴリズム

サイズnの問題があるとしましょう。現在、アルゴリズムの各ステップ（書き込みが必要）では、元の問題は以前のサイズの半分（n / 2）になります。

だから、それぞれのステップで、私たちの問題は半分になります。

問題空間が縮小された（すなわち完全に解かれた）場合、チェック条件を終了しても、それ以上縮小することはできません（nは1に等しくなります）。

1. k番目のステップまたは操作の数で言えましょう：

   問題サイズ = 1

2. しかし、私たちはk番目のステップで、私たちの問題の大きさは、

   問題サイズ = n / ^2k

3. 1と2から：

   n / 2 ^k = 1または

   n = ^2k

4. 両側にログを取る

   log _e n = k log _e 2

   または

   k = log _e n / log _e 2

5. 数式ログを使用する_x m / log _x n = log _n m

   k = log ₂ n

   または単にk = log n

今、私たちのアルゴリズムはlog nまで最大で実行できることを知っています。したがって、時間の複雑さは次のようになります。
O（log n）

上記のテキストをサポートするためのコードの簡単な例は次のとおりです。

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

だから、もしnが256であれば、もしあなたがループしている（または問題の大きさを半分に減らす他のアルゴリズム）ステップ数が非常に簡単に計算できるかどうかを尋ねるなら、

k = log ₂ 256

k = log ₂ 2 ⁸ （=> log _a a = 1）

k = 8

同様の場合の別の非常に良い例は、 バイナリサーチアルゴリズムです。

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}