빅오 표기법 (Big-O)
빅오 표기법이란 ?
연산의 횟수를 대략 표기한 것
설명하기 전에 시간 복잡도의 정의를 알아야 한다.
시간 복잡도는 어떤 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 시간으로 설명하는 계산 복잡도를 의미한다.
그리고 이러한 계산 복잡도를 표기하는 방법중 하나가 빅오 표기법이다.
예를 들어보자
분모가 계속해서 커지는 분수를 생각해보면 쉽다.
1/∞ 은 결국 0에 수렴하고 분모가 어떤 상수가 와도 결국엔 0으로 수렴한다.
빅오 표기법도 같다. 4n^2 + 3n +4 이 수식에서 n이 무한대로 커진다고 생각해보자.
일단 상수항 4는 의미가 없어진다. 그리고 3n도 4n^2이 엄청나게 커지면 의미가 없으므로 제외한다.
결국 위 식에서 남는 것은 최고차항인 n^2만 남는다.
그럼 빅오 표기법에는 어떤 것들이 있을까 ?
- O(1) : 상수형
- 입력값에 상관없이 일정한 실행시간을 가진다. 하지만 상수값이 매우 클 경우 의미가 없어진다.
- O(log n) : 로그형
- 매우 큰 입력값에서도 크게 영향을 받지 않는다. 따라서 매우 견고하다. (이진 탐색)
- O(n) : 선형
- 정렬되지 않은 리스트에서 최대 또는 최솟값을 찾는 경우에 해당된다. 모든 입력값을 한 번씩 살펴봐야 한다.
- O(n log n) : 선형로그형
- 아무리 좋은 알고리즘이라 할지라도 선형 로그형보다 빠를 수 없다. 대부분 효율이 좋은 알고리즘이 이에 해당한다. (병합 정렬)
- O(n^2) : 2차형
- 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
- O(2^n) : 지수형
- 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당한다. (n^2 << 2^n)
- O(n!) : 팩토리얼형
- 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.
알고리즘의 수행시간
알고리즘의 수행시간은 입력자료 집합에 따라 다를수
있다.
- 최선 : 수행 시간이 가장 빠름
- 의미가 없는 경우가 많다.
- 평균 : 수행 시간이 평균적임
- 계산하기가 상당히 어렵다.
- 최악 : 수행 시간이 가장 늦음
- 가장 널리 사용된다. 이유는 계산하기 쉽고 응용에 따라서 중요한 의미를 있을 수도 있기 때문이다.
글을 마치며
강의 시간에 배운 내용이 이해되지 않아서 따로 공부하여 이해한 내용을 정리해봤습니다.
혹시 다르게 이해했거나 틀린 부분이 있으면 지적도 달게 받겠습니다.
끝까지 읽어주셔서 감사합니다.
반응형
