[개발자 면접] Big-O Notation 빅오 표기법과 시간 복잡도

 

 

빅오는 개발자 면접 준비중이라면 무조건 마스터 해야하는 컨셉이다. 왜나면 기술 면접에서 빅오에 관련된 질문이 나올 확률이 99%이기 때문이다. 알고리즘의 시간 복잡도를 설명하기 위해서는 필수적으로 알아야한다.

 

 

빅오는 알고리즘이 얼마나 빠르게 실행될지를 비교할때 사용된다. 시간 복잡도 (Time complexity)를 통해서 알고리즘의 빠르기를 비교할 수 있다.

 

 

빅오(O), 오메가(Ω) , 세타 (Θ)

시간 복잡도를 표기 할때는 빅오만 이용한는 것이 아니다. 빅오, 빅 세타, 빅 오메가를 이용해서 최악의 경우, 평균의 경우, 최상의 경우를 표기한다.

 

Big-O Notation O(n): 최악의 경우

Big-Theta Notation Θ(n): 평균의 경우

Big-Omega Notation Ω(n): 최상의 경우

 

최악의 경우, 평균의 경우, 최상의 경우와 같이 세가지 표기법이 있는데 왜 알고리즘을 평가할때 보통 최악의 경우를 볼까?

 

그 이유는 최상의 경우는 별로 유용한 정보가 아니기 때문이다. 사실상 대부분의 알고리즘에 특별한 입력값을 이용하면 O(1)을 달성 할 수 있을 것이다. 

 

대부분의 알고리즘의 평균의 경우와 최악의 경우는 같다. 가끔은 다르기도 하지만 그럴 경우에도 최악의 경우를 보는 것이 최선이다. 그렇게 때문에 면접에서는 빅오 표기법을 많이 사용한다. 

 

 

보통 쓰이는 빅오: (빠른 순서대로)

O(1) 상수 시간

O(log N) 로그 시간

O(N) 직선적 시간

O(N log N) N 로그 N 시간

O(N²) 2차 시간

O(2^N) 지수 시간

 

보통 알고리즘의 시간 복잡도를 설명할 때 위에 표기를 이용한다. 여기서 상수 시간이 제일 빠르고 지수 시간 제일 느리게 실행된다.

 

 

빅오 계산하는 방법

1. 계수는 버려라

O(2N)은 O(N)으로 표시할 수 있다. 빅오는 실행속도가 얼마나 빠르게 비율적으로 자라는지 표시하는 것이기 때문에 계수를 쓰는 것은 쓸모가 없다. 

 

2. 식의 차수/우세한 항을 이용하라

만약 함수 표현이 다항식이라면, 식의 차수가 제일 높은 항이나 우세한 항으로 빅오를 표기하면 된다. 

 

예시:

• O(n² + n) 같은 식이 있다면 여기서 두번째 항인 n은 중요하지 않다. O(n²)으로 표기한다.

 

• O(n + n log n) 은 O(n)으로 표기한다. O(n)이 O(n log n)보다 느리기 때문이다.

 

• O(100n¹⁰⁰ + 10*2ⁿ) 은 더 우세한 항인 2ⁿ을 이용해서 O(2ⁿ)으로 표기한다.

 

만약 변수의 값에 대한 지식이 없다면 O(A + B)와 같이 다항식으로 빅오를 표현 할 수도 있다. (어떤 변수가 더 우세할지 모르는 경우)

 

3. 덧셈 vs 곱셈

만약 알고리즘이 여러 부분으로 나누어져 있다면 더해야할때가 있고 곱해야 할 때가 있다. 한 실행문을 하고 다음 실행문을 하는 경우 덧셈을 이용한다. 하지만 실행문 안에 실행문이 있다면 곱셈을 이용한다.

 

덧셈 경우:

for (x in arrayX) {
    console.log(x);
}

for (y in arrayY) {
    console.log(y);
}

위의 예시에서는 x만큼 실행한 후 y만큼 실행 한다. 그러므로 총 시간 복잡도는 O(x + y) 이다.

 

곱셈 경우:

for (x in arrayX) {
    for (y in arrayY) {
        console.log(x + ", " + y);
    }
}

이번 예시에서는 y만큼의 실행문을 x만큼 돌린다. 그러므로 총 시간 복잡도는 O(x * y) 이다.

 

 

로그 런타임 (log N)

로그로 표현되는 알고리즘들은 대부분 문제가 반토막이 나는 경우이다. Binary Search와 같이 문제의 크기가 계속 절반으로 작아지는 경우 O(log N)으로 표현한다. 

 

*여기서 로그의 밑은 빅오에서 상관이 없다

 

 

**Cracking the Code Interview 6th Edition을 읽고 정리한 내용입니다.