ComputationalComplexity를 표기하는 방법중 하나로써 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!)
집합의 모든 순열을 생성하는것