BigOシンボル

📝BigOマーク法とは?

🔖Big O?

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

🔖大O特性

🔖時間の複雑さとは?

🔖空間の複雑さとは?

📝時間の複雑さから見た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

//예제(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);
}

🔖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

📌の最後の部分