반응형
코딩 테스트를 준비하면서 가장 먼저 기본을 다져야 할 부분은 바로 Big-O 계산이죠.
Big-O는 알고리즘의 효율성을 나타내는 지표 혹은 언어입니다.
Big-O 계산법
1. 상수항은 무시하라
big-O는 단순히 증가하는 비율을 나타내는 개념입니다.
특수한 입력에 의해 O(n)이 O(1)보다 더 빠를 수 있죠. N이 1/2이라면요. (아주 특수한 입력이기 때문에 무시)
그렇지만 앞서 이야기 드렸던 것처럼 증가하는 비율을 나타내는 개념이기 때문에 상수항은 그냥 무시한다고 보시면 됩니다.
따라서 O(2N)이 있다면 빅오 표기법으로는 O(N)으로 표기하시면 됩니다.
2. 지배적이지 않은 항은 무시하라
앞서 상수항은 무시해도 된다고 언급했던 것처럼 같은 원리입니다.
O(N^2 + N) 의 경우는 O(N^2) 이라고 보면되죠. N은 N^2에 비해 지배적이지 않은 항이기 때문입니다.
마찬가지로 O(N+logN)의 경우는 O(N)이 됩니다.
이 경우는 어떨까요?
O(B^2+A)
이 경우는 하나의 항으로 줄일 수 없습니다.
A와 B는 각각의 변수죠. 둘의 관계를 알 수 없는 한 줄일 수 없습니다.
반응형