Complexity

時間複雑度バー
演算と回数を計算するのに時間ではなく、時間の複雑さと呼ばれます.
big−o記号では、最長時間または大量の空間を必要とする場合を表す.
スペースマークはあまり使いにくいそうです.

- Time Complexity

Big-O-Notation:タグが最悪のアルゴリズム

の数字は無視されます.(2 nの場合はnで表す)

の低次数が消去されます.(n^2+2 n+3をn^2と表記します.)

O(n^2) : Quadratic

象限の例

二重複文では、対応する演算回数がn*nの場合、O(n^2)と表記する.

演算

の回数は幾何級数的に増加した.そのため、1回増加するごとに2倍以上増加します.時間がかかります.

例えば

九九乗算、行列演算などである.

for(i=0; i < N; i++) 
{
    for(j=0; j < N;j++)
    { 
    statement;
    }
}

O(n) : Linear

Linearの例

これは、演算回数

に応じて用いられるマーキング法である.O(n)とマークされ、文の演算を繰り返すと、時間の複雑さは線形図に従います.

出力

1−10での時間的複雑度はO(n)である.

for(i=0; i < N; i++)
{
    statement;
}

O(log n): Logarithmic

Logarithmic

アルゴリズムの実行時間は、Nが2に分けられる回数に比例する(Nはここでは高い、低い).

演算で、半分に分かれた演算をO(logn)マーキング法と呼ぶ.

バイナリsearchを例に挙げます.下図に示すように、binary searchを使用して6を検索する場合は、まず1から10の中間値を検索し、検索する値(6)より大きいかどうかを決定します.確認した結果は6より小さいので、5以下で検索する必要はありません.次に、6～10の間に中間値を見つけて比較します.中間値は8で8未満なので、8以上見る必要はありません.残りの数は六七で、探している数に比べて探せば終わりです.このように3回の演算を経て,時間が大幅に減少した.O(n)で記述したアルゴリズムに比べて時間がかなり短縮されていることが分かる.

while(low <= high) 
{
    mid = (low + high) / 2;
    if (target < list[mid])
        high = mid - 1;
    else if (target > list[mid])
        low = mid + 1;
    else break;
}

O(1) : constant

定数は、データ量が大きくても一度だけ計算される時間的複雑さを表す.

の例では、配列内で特定のインデックスを問合せたい場合、時間的複雑度はO(1)です.

時間複雑度の高速ソート
O(1)>O(logn)>O(n)>O(n^2)>O(2^n)の順で時間の複雑さが長い.