[알고리즘] 빅오

빅오(Big O notation)

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or inifinity.

빅오 표기법이란 입력값이 특정값 혹은 무한대를 향할 때 limit 함수의 실행 시간 추이를 표현하는 수학적 표기법이다.

빅오는 시간 복잡도와 공간 복잡도를 표현하는데 사용된다. 즉 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도는 시간 복잡도이고, 그에 필요한 공간 요구사항을 설명하는 계산 복잡도는 공간 복잡도이다.

빅오 표기법의 종류(시간 복잡도)

O(1)

입력값이 아무리 커도 실행 시간은 일정하기 때문에, 최고의 알고리즘이라고 할 수 있다. 예시로는 해시 테이블의 조회와 삽입이 있다.

O(log n)

로그 특성 상 입력값이 매우 커도 크게 영향을 받지 않기 때문에, 실행 시간 자체는 빠르다고 볼 수 있다. 예시로는 이진 검색이 있다.

O(n)

선형 시간 알고리즘이라고도 하며, 여기서는 모든 입력값을 적어도 한번씩은 살펴봐야 한다.

O(n log n)

대부분 효율이 좋은 정렬 알고리즘이 이에 해당한다.

O(n^2)

선형 시간 알고리즘보다 더 비효율적이다. 하지만 O(2^n)에 비해서는 시간복잡도가 작다.

알고리즘은 시간, 공간이 trade-off 관계이다. 즉, 실행 시간이 빠르면 공간을 많이 사용하고, 공간을 적게 차지하면 실행 시간은 느릴 수 밖에 없다.