빅오 표기법

빅오 표기법의 특징

상수항을 무시하고 오직 가장 큰항만을 고려하여 표기한다. 그 이유는 데이터가 커질 수록 최고차항이외의 항이 가지는 연산의 의미는 감소하기 때문이다.

위의 그림에 따르면

상수<로그<선형함수<다항함수<지수함수 순으로 시간 복잡도가 증가하는 추세를 보인다.

빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 될 것 같다.

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. 지수 함수는 피보나치 수열