알고리즘 BigO 간단 정리

빅오 표기법의 그래프는 x축은 입력의 갯수, y축은 시간을 나타낸다.

 

출처 : http://bigocheatsheet.com/

---

빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하는 기법이다.
보통 O(n)과 같이 표기하며 여기서 n은 입력의 개수를 의미한다.
따라서 n이 무한으로 접근할 때 무슨일이 일어날까? 정도로 생각하면 좋을 듯 하다.

가장 빠른 순

O(1) ->O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) 

Loof 내에서 Loof를 돌면? (이중 for문)

public class Main {

    public static void printItems(int n) {
        for (int i =0; i<n; i++){
            for(int j =0; j<n; j++){
                System.out.println(i + " " + j);
            }
        } 
    }


    public static void main(String[] args) {
        printItems(10);
    }
}

=> 0 0 ~ 9 9까지  총 100번 호출

-> O(n^2)

O(100n^2)는 빅오 표기법으로 어떻게 쓰여질까?

-> O(n^2) n^2이란 숫자는 지배적으로 거대하게 커지는 숫자이므로, 상대적으로 비지배적인 상수는 제거하여 간략하게 쓰여진다.

ex) O(n^2 + n)  -> O(n^2)가 된다. (n제곱이 지배적인 값이기 때문에)

분할&정복에 관련된 빅오는?

-> O(log n)