빅오 (Big-O)에 대해..

목차

빅오 표기법이란 입력 크기가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법

알고리즘은 궁극적으로는 컴퓨터로 구현되는데 컴퓨터의 빠른 처리 능력이라면 아무리 복잡한 알고리즘이라도 입력 크기가 작으면 금방끝나버린다. 그러므로 입력의 크기가 충분히 클 때에 관심을 갖는 것.

 

[Big-O ?]

빅오 표기법에서 "점근적"이라는 개념은, 입력 크기 n이 매우 커질 때(즉, 무한대에 가까워질 때) 알고리즘의 실행 시간이나 공간 사용량이 어떤 상한선에 점점 가까워지는 지를 표현하고자 할 때 사용하며 가장 흔히 쓰이는 것이 시간복잡도이다.

 

빅오를 표현할 때는 최고차 항만을 표기하며, 계수는 무시한다. 구체적인 실행시간이 아니라 실행시간의 추이만 살펴보기 때문이다.

 

 

• O(1): 상수 시간 – 입력 크기에 상관없이 항상 같은 시간이 걸림.
• O(log n): 로그 시간 – 입력 크기가 커질수록 시간이 천천히 증가.
• O(n): 선형 시간 – 입력 크기에 비례해서 시간이 증가.
• O(n log n): 로그 선형 시간 – 입력 크기가 커질수록 로그와 선형 증가의 결합.
• O(n²): 이차 시간 – 입력 크기에 제곱으로 시간이 증가.
• O(2ⁿ): 지수 시간 – 입력 크기가 커질수록 시간이 매우 빠르게 증가.
• O(n!): 팩토리얼 시간 – 입력 크기가 커질수록 시간이 매우 빠르게 증가(지수보다 훨씬 느림).

[Big-O 표기법 종류]

O(1)

입력값이 아무리 커도 실행시간이 일정.

public int fn(int n) {
	return 42; 
}

 

 

위의 함수는 n의 크기가 얼마든 항상 같은 실행시간이다. O(1)의 실행시간의 예시는 배열에서 값을 조회할 때, 연결리스트의 끝에 값을 삽입할 때 등이 있다.

 

O(log n)

public int fn(int n) {
    while (n > 1) {
        n /= 2;
    }
    return n;
}

 

O(log n)의 경우 입력 크기에 비례하지 않고, 크기를 반씩 줄여나가는 상황에서 발생한다.

Binary Search 같은 경우 배열을 매번 절반으로 나누면서 검색하기 때문에 이에 해당한다.

 

O(n)

정확히 입력값의 크기만큼 실행시간에 영향을 받는다.

public int fn(int n) {
    int r = 0;
    for (int i = 0; i < n; i++) {
        r++;                        
    }
    return r;
}

 

실행시간이 선형으로 증가하기 때문에 O(n)을 선형 시간 알고리즘 이라고도 부른다.

정렬되지 않은 리스트에서 최대/최소 값을 찾으려면 처음 모두 찾아야 하므로 O(n) 만큼 걸린다.

 

O(n log n)

입력 크기에 비례하면서, 동시에 각 단계에서 로그 함수를 수행하는 경우 나타납니다.

public int fn(int n) {
	int r = n;
    for (int i = 0; i < n; i++) {
        while (n > 1) {
            n /= 2;            
        }   
        n = r;
    }    
    return r;
}

 

위의 함수는 n의 크기 만큼 순회하면서 내부적으로 입력 값을 다시 반으로 나눠가며 log n의 연산을 진행하고 있다.

 

병합 정렬 (merge sort)은 배열을 두 부분으로 계속 나누면서 각 부분을 재귀적으로 정렬한 후 마지막에 두 부분을 병합하는 과정으로 이루어지므로 O(n log n)이 소모된다.

 

• 분할 단계: 배열을 두 부분으로 나누는 작업이 있는데 배열을 계속 반으로 나누기 때문에 log n 단계가 필요
• 병합 단계: 배열을 다시 병합할 때는 각 단계에서 배열 전체를 훑어야 하므로 n번의 연산이 필요

힙 정렬도 배열을 힙 구조로 만들고, 최대값을 루트에서 제거하면서 정렬을 수행

• 힙을 만드는 데 드는 시간은 n
• 힙에서 요소를 제거하는 과정에서 힙을 재정렬해야 하는데, 이 과정은 log n의 시간이 소요

 

적어도 모든 수에 대해 한 번 이상을 비교해야하는 비교 기반 정렬 알고리즘은 아무리 좋아도 O(n log n)보다 빠를 수 없다고 한다.

또한 실용적인 관점에서 O(n)이나 O(n log n)은 사실상 비슷한 성능으로 가정해도 무방하다고 한다.

 

O(n^2)

입력 값의 제곱만큼 연산

public int fn(int n) {
        int r = 0;
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                        r+=j;
                }
        }
        return r;
}

 

n의 크기만큼 다시 n번 연산한다.

버블정렬이 여기에 해당하며 n^2 부터는 타임아웃이 발생할 가능성이 높아진다.

 

O(2^n)

입력값의 크기만큼 2배씩 연산한다.

public int fn(int n) {
        if (n <= 1) {
                return n;
        } else {
                return fn(n - 1) + fn(n - 2);
        }
}

 

위 함수는 피보나치 수를 재귀로 계산하는 알고리즘인데 입력 값 n의 2배 만큼의 연산을 수행하고 있다.

n^2과 비슷해보이지만 사실 2^n이 훨씬 더 크다고 한다.

 

일반적으로 재귀 알고리즘은 실행하는 데 O(2^n)이 걸리는 비효율적인 알고리즘이다. 하지만 메모이제이션과 같은 기법을 활용하면 실행시간은 O(n) 까지 줄일 수 있다.

O(n!)

입력 값을 1씩 줄여가며 곱셈 연산을 하는 경우다.

public int fn(int n) {
        for (int i = 0; i < n; i++) {
                fn(n-1);
        }
        return n;
}

 

 

O(n!)은 매우 느린 알고리즘으로 입력 값이 조금만 커져도 웬만한 시간에는 계산이 어렵다. 그러므로 코딩테스트나 실무에서는 사실상 적용이 어려운 알고리즘이라고 한다.

 

[Big-O를 계산하는 실용적인 방법]

빅오는 헷갈릴 때가 많다고 한다.

public int factorial(int n) {
        if (n >= 1) {
                return n * factorial(n - 1);
        }
        else {
                return 1;
        }
}

 

위의 함수는 재귀도 있으니 O(n!) 로 생각해볼 수 있다. 하지만 실제로는 O(n) 이라고 한다.

함수의 count를 계산해보자.

int count = 0;
public int factorial(int n) {
        if (n >= 1) {
                count++;
                return n * factorial(n - 1);
        }
        else {
                count++;
                return 1;
        }
}

 

그럼 그 결과가 아래와 같으며 결국 O(n+1)이다. 상수는 생략하므로 O(n)이 된다.

factorial(5) = 6

factorial(6) = 7

factorial(7) = 8

 

[자바 컬렉션 프레임워크의 빅오]

리스트의 시간 복잡도

연산	ArrayList	LinkedList
인덱스 끝에 삽입	O(1), O(n) (공간이 가득찰 경우 더블링)	O(1)
인덱스 중간에 삽입	O(n)	탐색 O(n), 삽입 O(1)
인덱스 끝에서 삭제	O(1)	O(1)
인덱스 중간에서 삭제	O(n)	탐색 O(n), 삭제 O(1)
조회	O(1)	O(n)

 

ArrayList는 배열 중간에 삽입/삭제할 수 없어서 새로운 공간에 복사해야한다. 그러므로 O(n)이 걸린다.

LinkedList는 삽입 자체는 노드를 연결해주면 되기만 하기 때문에 O(1)이지만 중간에 삽입할 때는 노드를 처음부터 탐색해야해서O(n)이 소요된다. 조회의 경우 O(n)이나 소요되기 때문에 조회가 잦다면 LinkedList의 사용은 지양해야 하는 것이다.

 

하지만 실제로 ArrayList, LinkedList의 삽입 연산을 해보면 LinkedList가 더 오래 걸린다고 한다.

그 이유는 LinkedList의 경우 메모리를 할당해야 하는 등 더 비싼 작업이 수행되기 때문이다.

 

중간에서 삭제하는 연산의 경우 동일한 시간복잡도이지만 ArrayList의 속도가 더 느리다.ArrayList는 삭제 후 새로운 공간에 복사해야되고, LinkedList는 탐색 후에 연결만 바꿔주면 되기 때문이다.

 

맵의 시간 복잡도

연산	HashMap	LinkedHashMap
추가	O(1)	O(1)
삭제	O(1)	O(1)
조회	O(1)	O(1)

 

Map은 해시테이블 기반으로 구현되어 있어서 모두 O(1)로 가능하다.

키 값이 주어지면 해시함수를 돌려 해시값을 얻게되는데 그걸 인덱스로해서 메모리의 슬롯에 바로 접근할 수 있기 때문이다.

 

다만 LinkedHashMap의 경우 순서를 보장하기 위해 연결리스트를 사용하기 때문에 HashMap보다는 살짝 더 느리다고 한다.

 

데크 시간 복잡도

데크는 양쪽에서 삽입과 삭제할 수 있는 자료형이다.

자료형의 성격상 이중 연결 리스트가 어울리기 때문에 LinkedList의 계열로 생각할 수 있지만 실제로는 ArrayDeque이라는 동적배열 기반으로 구현되어 있다고 한다.

연산	ArrayDeque	LinkedList
삽입	O(1)	O(1)
추출	O(1)	O(1)

 

데크는 스택과 큐를 대체하는 역할을 하며 Stack, Queue에 비해 성능적으로 유리할 수 있다.

 

 

• ArrayDeque는 동적 배열을 기반으로 구현되어 있어, **상수 시간 O(1)**의 성능으로 요소를 추가하거나 제거할 수 있음. 양쪽 끝에서의 삽입과 삭제가 빠르기 때문에 스택과 큐로 사용하기에 적합
• Stack은 비록 LIFO(Last In First Out) 구조이지만, Vector를 상속받아 내부적으로 배열을 사용하고 있어 성능이 떨어질 수 있다.
• Queue는 기본적으로 연결 리스트를 기반으로 하여, LinkedList의 인스턴스가 사용되며, 배열 기반의 ArrayDeque는 일반적으로 더 좋은 캐시 성능을 가지고 있음.

 

삽입과 추출 과정을 ArrayDeque, LinkedList를 비교해보면 삽입의 경우 ArrayDeque의 경우 동적배열 기반으로 가끔 더블링 정도만 발생한다. 하지만 LinkedList의 경우 새로운 Node를 만드는 과정이 있기 때문에 결국 ArrayDeque가 더 빠르다.

삭제의 경우 ArrayDeque는 배열을 축소하는 과정이 필요하지만 LinkedList의 경우 연결만 변경해주면 되기 때문에 상대적으로 LinkedList가 좀 더 빠르다.

 

어쨋든 결론은 ArrayDeque는 스택과 큐의 특성을 모두 가지고 있는데 LinkedList와 비교했을 때 삭제측면에서는 비슷하더라도 삽입과정에서 성능적으로는 더 우수하기 때문에 ArrayDeque를 사용하는 것을 권장한다고 한다.