시간 복잡도

[”apple”, “banana”, “grape”, “pear”, “melon”]

위와 같은 과일 배열이 있다.

“melon”을 검색하기 위해서 index 0부터 … index 4까지 탐색한다.

이 때는 원소의 개수인 5개만큼 단계가 실행 (5단계) 되었으므로

O(N)의 시간 복잡도를 가진다.

반면, “apple”을 검색하기 위해서 index 0부터 탐색하는데,

바로 첫 단계에서 발견했기 때문에 O(1)의 시간복잡도를 가진다.

하지만, 시간 복잡도 계산은 최악의 시나리오를 채택하기 때문에

O(N)의 시간복잡도를 가지게 된다.

반면, 이진 탐색의 시간 복잡도는 어떨까?

만일 “grape”를 검색한다면 O(1)의 시간 복잡도를 가질 것이고,

절반씩 잘라 탐색하기 때문에 원소의 개수보다는 적은 단계를 갖기 때문에

O(1)과 O(N) 사이 어딘가의 시간 복잡도를 가질 것이다.

때문에, 이진 탐색은 O(log N)의 시간 복잡도를 가진다.

이 때 log는 밑이 2인 로그, 즉 이진 로그 (lb) 이다.

O(log N)은 데이터(N)가 두 배로 증가할 때마다 단계가 한 단계씩 증가한다.

예를 들어, log2 일때는 1단계, log4 일때는 2단계, log8 일때는 3단계

… log1024 일때는 10단계가 걸린다.

그래프와 표를 보며 O(N)과 O(log N)의 차이를 알아보자.

O(N)은 원소의 개수가 늘어날 수록 비례로 단계가 늘어난다.

반면, O(log N)은 원소의 개수가 (data) 두배가 될 때마다 한 단계식 늘어난다.

알아본 세가지 빅오 외에도,

O(N log N), O(N^2), O(2^n)이 있다.

각각 예제만 간단히 알아보자.

1. O(1) : Push, Pop, console 등
2. O(log N) : 이진 탐색
3. O(N) : for 문
4. O(N log N) : 퀵 정렬, 힙 정렬, 병합 정렬
5. O(N^2) : 이중 for문, 삽입정렬, 버블정렬, 선택정렬
6. O(2^n) : 피보나치 수열