BioHackersNetComputationalComplexity를 표기하는 방법중 하나로써 [Algorithm]의 성능을 정형적으로 표현하는 일반적인 표기법. SeeAlso EstimateOrderOfAlgorithm
보통 알고리즘의 성능은 수행하는 자료의 크기(n)의 함수로 표현된다.
간단한 규칙들
- O(c) = O(1) : 상수항. 자료의 양에 관계없이 일정한 시간이 걸릴경우.
- O(cT) = cO(T) = O(T) : 계수들은 생략한다.
- O(T1) + O(T2) = O(T1 + T2) = max(O(T1), O(T2)) : 더할때는 큰것을 선택.
- O(T1)O(T2) = O(T1 T2) : 곱은 간결히
따라서, 다음처럼 표현한다.
일반적인 문제별 BigOhNotation
BigOhNotation |
example |
O(1) |
자료의 집합에서 첫번째 항목가져오기 |
O(lg n) |
자료의 집합을 반으로 나누고 그 반을 다시 반으로 나누는 과정의 반복 |
O(n) |
자료집합을 순회하기 |
O(n lg n) |
자료집합을 반복해서 둘로 나누고 나뉘어진 반을 순회하는것 |
O(n^2) |
한 집합의 각자료에 대해 같은 크기의 다른 집합을 순회하는것 |
O(2^n) |
집합의 모든 부분집합을 생성하는것 |
O(n!) |
집합의 모든 순열을 생성하는것 |