Big O 시간 복잡도란?

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

Big O 표기법은 입력 크기가 커질 때 연산량이 어떤 속도로 증가하는지 표현한다. 정확히 몇 나노초가 걸리는지를 말하는 벤치마크와는 목적이 다르다.

자주 보는 복잡도

O(1)       배열 인덱스 접근
O(log N)   이진 탐색
O(N)       전체 순회
O(N log N) 일반적인 비교 정렬
O(N²)      모든 쌍 비교

상수는 생략한다

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

두 번 순회하므로 실제 연산은 2N에 가깝지만 Big O에서는 O(N)으로 표현한다. N이 커질 때 증가하는 차수에 집중하기 때문이다.

상수를 무시한다고 실제 성능에서 상수가 중요하지 않은 것은 아니다. 캐시 친화적인 O(N) 코드가 복잡한 상수를 가진 다른 O(N) 코드보다 훨씬 빠를 수 있다.

최악, 평균, 최선

선형 탐색은 첫 원소에서 찾으면 O(1)이지만, 없거나 마지막에 있으면 O(N)이다. 어떤 경우를 말하는지 적지 않으면 같은 알고리즘을 서로 다르게 설명하게 된다.

Big O는 알고리즘을 고르는 첫 번째 필터다. 최종 선택은 실제 데이터 크기, 메모리 사용량, 캐시, 구현 복잡도와 함께 판단해야 한다.