빅오 표기법 개념과 예제

Big-O(빅오) 표기법

알고리즘의 성능 및 복잡도를 표현하기 위하여 사용하는 지표

알고리즘의 실행 시간 또는 사용 메모리 공간을 표현

정확한 값이 아닌 어림 값으로, 알고리즘의 대략적인 평가만 가능

시간복잡도, 공간복잡도

시간복잡도

1) 알고리즘의 실행 속도를 측정(CPU)
2) 표기법은 (4.표기법 및 종류) 참고 3) O(n2)포함해서 더 느린 알고리즘은 좋지않다고 판단 - 공간복잡도

1) 알고리즘이 사용한 메모리를 측정(RAM) 2) 크기가 N인 배열이 N*N배열 되었을 경우 공간 복잡도는 N2

아래 사진을 통해 빅오 표기법을 알아보면 대충 이해가 갈 것이다.

O(1)쪽으로 갈 수록 속도가 빠른 것이고, O(N2)에 갈 수록 속도가 느려진다.

O(1)

인자에 값이 여러개 있더라도 하나에 접근했을 때 O(1)이 된다.

해쉬 테이블에 접근하거나, 스택에서 Push, Pop을 했을 때 O(1)이 된다.

1 2 3 4

public static void main(String[] args) {     int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };     System.out.println(arr[0]); }

O(log n)

이진 트리가 있는데 2를 찾으려고 하면 5에서 1번 비교하고, 3에서 한번 비교를 해서 2를 찾을 수 있었다.

그래서 log 4 = log 2^2가 됩니다. log n을 나타내는 것으로는 이진 탐색을 예로 들 수 있다.

O(n)

아이템의 개수 만큼 Access를 하기 때문에 O(n)이다. 

O(n)의 예를 들자면 트리 선회를 들 수 있다.

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    for(int i=0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

O(n log n)

쉽게 설명을 하기 위해 합병 정렬을 예로 들겠다.

합병 정렬을 맨위에서 아래 8, 4, 5, 2 까지 내려가는데 2번이 걸렸다. 그래서 log 2^2가 나왔고, 하나 하나 나누어진 수를 다시 정렬하여 합치는데 n만큼 각자의 아이템을 비교하기 때문에 n이 나온다. 그래서 O(n log n)이 된다.

n log n이 걸리는 것은 퀵정렬, 합병정렬이 있다.

O(N2)

아래 예제는 버블 정렬인데 버블 정렬을 하기 위해서는 for문을 2번 돌아야 한다. for문을 1번 돌 때 n만큼 돌아야 하고, for문 안에서 또 n만큼 루프를 돌아야 하기 때문에 O(N2 )이 된다. O(N2 )의 예를 들자면 버블, 삽입, 선택 정렬을 들 수 있다.

public static void main(String[] args) {
    int[] arr = {0, 11, 9, 5, 4, 3, 1, 8, 10 };
    
    for(int i= arr.length; i > 0; i--) {
        for(int j=1; j < i; j++) {
            if(arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}