빅오 표기법 (big-O notation) 이란?

빅오 표기법은 시간 복잡도와 공간 복잡도를 나타낼 수 있다.
시간 복잡도는 어떤 알고리즘을 실행하는데 걸리는 시간을 의미한다.
이 시간 복잡도를 표기하는 방법은 빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법 등이 있다.
또한 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.

시간복잡도 vs 공간복잡도

시간복잡도와 공간복잡도는 반비례한다.
즉, 실행시간이 빠른 알고리즘은 공간을 많이 차지하고, 공간을 적게 차지하는 알고리즘은 실행하는 시간이 느려진다.

빅오(Big-O)

시간의 효율성을 상한선으로 표현한다.
즉 최대 00시간이 걸린다는 뜻이다.
주의할 점은 빅오 표기법이 상한선만 지정했을 뿐이고 그 상한선이 꼭 알고리즘 효율성의 최악의 경우는 아니다.

빅오메가(big-Ω)

시간의 효율성을 하하선으로 표현한다.
즉, 적어도 00시간이 걸린다는 표현이다.

빅세타(big-Θ)

시간의 효율성을 상한선과 하한선을 모두 보여주어 표현한다.
즉, 어떤 알고리즘을 실행하는데 00과 AA사이의 시간이 걸린다고 표현한다.

빅오 표기법 성능 비교

오른쪽으로 갈 수록 더 느려진다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)

빅오 표기법 수학적 정의

모든 n>=n₁>0 0<=f(n)<=kㆍg(n)인 양의 상수 k와 n₁이 존재하면 f(n) = O(g(n))이다

만약
f(n) = n²+4n+2
g(n) = n²
이라면
n=3일때, n₁은 1,2이되고

f(n)<=kㆍg(n)에서
n=1 -> f(n) = 7, g(n) = 1 -> k=7이상
n=2 -> f(n) = 14, g(n) = 4 -> k=4이상

따라서
빅오 표기법으로 f(n) = O(n²)라고 구할 수 있다.

빅오 표기법 종류

O(1)

일정한(상수의 시간)을 같는 알고리즘이다. 입력값과 상관없다.
최고의 알고리즘이라 생각할 수 있겠지만 상수 값이 매우 크다면 효율적이지 않다.
따라서 최고의 알고리즘이 될 수 있으나 그 만큼 신중해야한다.
👀ex) 해시 테이블의 조회 및 삽입, 스택에서 Push, Pop

O(log n)

로그는 매우 큰 입력값에도 크게 영향을 받지 않는다. 따라서 웬만한 n(입력값)의 크기에도 매우 견고하다.
👀ex) 이진검색(이진트리)

O(n)

선형시간(Linear-Time) 알고리즘이라고 한다. 수행시간이 입력값에 비례하며
정렬되지 않은 리스트에서 최댓값, 최솟값을 찾는 경우가 이에 해당한다.
이 값을 찾기 위해서는 모든 입력값을 적어도 한번 이상은 살펴봐야 한다.
👀ex) for 문

O(n log n)

병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.
적어도 한번 이상은 비교하는 기반 정렬 알고리즘[O(n)]은 아무리 좋은 알고리즘 이라도 [O(nlog n)]보다 느리다.
👀ex) 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

O(n²)

버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
👀ex) 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

O(2ⁿ)

피보나치수를 재귀로 계산하는 알고리즘이 이에 해당한다.
n²와 처음은 비슷하지만 시간이 갈 수록 알고리즘 효율성이 좋지 못하다.
👀ex) 피보나치 수열

O(n!)

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

참고자료

1) https://noahlogs.tistory.com/27
2) https://velog.io/@dltjq2323/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%ED%9A%A8%EC%9C%A8%EC%84%B1%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EB%B9%85%EC%98%A4