[Hello Coding 알고리즘] 빅오 표기법

이 포스트는 “Hello Coding 그림으로 개념을 이해하는 알고리즘, 아디트야 바르가바”를 읽고 작성하였습니다.

빅오 표기법

$O(n)$ (n은 연산 횟수)

우리가 흔히 어떤 알고리즘이 얼마나 빠른지를 나타낼 때 빅오 표기법을 많이 쓴다. 참고로 알파벳 대문자 O를 쓰기 때문에 빅오(Big O) 표기법이라고 한다(맙소사…).

탄생 배경 및 개념

여러 알고리즘의 시간을 비교하기엔 각 알고리즘의 실행 시간이 같은 비율로 증가하지는 않는다. 예를 들어 단순 탐색이 100밀리초/100개, 10초/10,000개, 11일/1,000,000,000개 순으로 증가한다 하면, 이진 탐색은 7밀리초/100개, 14밀리초/10,000개, 32밀리초/1,000,000,000개 순으로 증가한다. 따라서 알고리즘의 실행 시간 뿐만 아니라 데이터의 개수가 얼마나 증가할 때, 시간이 얼마나 더 걸리는지도 고려해야 한다.

그래서 빅오 표기법은 알고리즘이 얼마나 빠른지를 알려주지만, 속도를 시간 단위로 측정하지 않는다. 즉, 연산 횟수를 비교하기 위한 표기법이다.

많이 사용하는 빅오 실행 시간

• $O(\log{n})$, 로그 시간: 이진 탐색
• $O(n)$, 선형 시간: 단순 탐색
• $O(n * \log{n})$: 퀵 정렬과 같이 빠른 정렬 알고리즘
• $O(n^2)$: 선택 정렬과 같이 느린 정렬 알고리즘
• $O(n!)$: 외판원 문제와 같이 정말 느린 알고리즘