BigOシンボル

📝BigOマーク法とは?

🔖Big O?

これは

アルゴリズムの性能を数学的に反映している.

時間複雑度または空間複雑度を表すことができる.

目標は、

データまたはユーザ成長率予測アルゴリズムの性能である.

🔖なぜBigOを使うのですか?

マーキング法の意味を理解すれば,複雑さをすばやく説明できる.
すなわち,アルゴリズム解析を迅速に行うことができる.

コードは、

の性能予測によって評価することもできる.

🔖大O特性

定数項は無視されます.

影響力のない港を無視します.
[例]
O(2N) → O(N)
:定数項は無視し,O(2 N)はO(N)で表す.
O(N²+N+1) → O(N²)
:無影響項を無視し、O(N)²+N+1はO(N)を表す²)に表示されます.

🔖時間の複雑さとは?

これは、

アルゴリズムを実行するのにどれだけのステップ(演算)が必要かを示す.
(※アルゴリズムの実行に要する時間の計算ではありません.)

🔖空間の複雑さとは?

これは、

アルゴリズムを実行するのにどれだけのメモリが必要かを示します.

📝時間の複雑さから見たBigOタイプ

🔖 O(1), Constant Time

入力データのサイズにかかわらず、アルゴリズムには常に一定の時間がかかります.

//예제(java code)
public boolean func(int[] n) {
    //배열 n의 크기와 상관없이 n[0]이 0이면 true를, 0이 아니면 false를 반환한다.
    return (n[0] == 0)? true : false;
}

O(1)をグラフィックで表す

-データが増加しても、時間は変わりません.
-つまり、データが増加してもパフォーマンスは変化しません.

🔖O(N), Linear Time

入力データのサイズに基づいて時間のかかるアルゴリズムを表す.

//예제(java code)
public void func(int[] n) {
    for(int i : n) { 
        System.out.println(i);  //배열 n의 크기만큼 출력을 수행한다.
    }
}

O(N)をグラフィックで表す

🔖O(N²), Quadratic Time

アルゴリズムの時間長は

入力データサイズの平方である.

//예제(java code)
public void func(int[] n) {
    for(int i : n) {
        for(int j : n) {
            System.out.println(i+j);  //배열 n의 제곱 크기만큼 출력을 수행한다.
        }
    }
}

O(N²)図形で表す

🔖O(NM)

入力データのサイズを乗算するアルゴリズムを表します.

//예제(java code)
public void func(int[] n, int[] m) {
    for(int i : n) {
        for(int j : m) {
            System.out.println(i+j);  //배열 n과 m 크기의 곱만큼 출력을 수행한다.
        }
    }
}

O(NM)をグラフィックで表す

🔖O(N³), Polynominal Time

入力データサイズの二乗に比例するアルゴリズムを表します.

//예제(java code)
public void func(int[] n) {
    for(int i : n) {
        for(int j : n) {
            for(int k : n) {
                System.out.println(i+j);  //배열 n의 크기 세제곱만큼 출력을 수행한다.
            }
        }
    }
}

O(N³)図形で表す

-データが増加するにつれてO(N)²)処理時間は、のグラフよりも急激に増加します.

🔖O(2ⁿ), Exponential Time

アルゴリズムの入力データサイズは

2の平方である.

フィボナッチ数列を例にとると,この複雑さは容易に理解できる.

//예제(java code) - 피보나치 수열을 구하는 재귀함수
public int func(int n) {
    if(n <= 0) { return 0; }
    else if(n == 1) { return 1; }
    return func(n-1) + func(n-2);
}

2479172 O(2ⁿ)をグラフィックで表す

-データが増加するにつれてO(N)²), O(N³)処理時間は、のグラフよりも急激に増加します.

🔖O(log n), Logarithmic Time

アルゴリズムの時間長は

ログ入力データのサイズと同じである.

バイナリ探索を例にとると,この複雑さは容易に理解できる.

//예제(java code) - Binary Search Tree
public void func(int key, int[] arr, int start, int end) {
    if(start > end) { return -1; }
    int mid = (start + end) / 2;
    
    if(arr[mid] == key) { return mid; }
    else if(arr[mid] > key) { return func(key, arr, start, mid-1); }
    else { return func(key, arr, mid+1, end); }
}

O(logn)をグラフィックで表す

−O(N)のグラフより処理時間が少ない.
-O(logn)のグラフは、データの増加がパフォーマンスにあまり影響しないことを示しています.

📌Reference

参照ビデオ1-BigO完全征服
備考ビデオ2-BigO 10分画像説明
参照ビデオ3-Arrayベース(+複雑度の説明)
注意:ブログ-スペースの複雑さ

📌の最後の部分

Big O Cheat Sheetでは、データ構造の複雑さのBigOマーカーが見られる.