빅오 (Big-o)

입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법입니다.
빅오는 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나이다.

접근적 실행 시간(Asymptotic Running Time)

입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행 시간 추이를 의미한다.
달리 말하면 시간복잡도라 할 수 있다.

시간 복잡도(Time Complexity)

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의마하며,계산 복잡도를 표기하는 대표적인 방법이 바로 빅오이다.

빅오 표기법의 종류

> 1. O(1)

입력값이 아무리 커도 실행 시간은 일정하다.
O(1)에 시행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.

2. O(logn)

실행 시간이 입력값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다.
대표적으로 이진 검색이 이에 해당.

3. O(n)

입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값이 비례하다.
이러한 알고리즘을 선형 시간 알고리즘이라고 한다.
정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

4. O(n logn)

병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.
입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트(Timsort)가 이런 로직을 갖고 있다.

5. O(n2)

버블 정렬 같은 비효율적 정렬 알고리즘이 이에 해당한다.

6. O(2n)

피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다.
n2보다 2n이 훨씬 크다.

7. O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당한다.가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.