빅-오 표기법(Big-Oh Notation)

시간 복잡도: 속도에 해당하는 알고리즘의 수행시간 분석결과

공간 복잡도: 메모리 사용량에 대한 분석결과

 

알고리즘의 최악의 경우(worst case)를 수식으로 만든 후 그 수식에서 가장 영향력이 큰 부분을 빅-오라고 한다.

 

예)

T(n)= n^2+2n+1의 빅오는 O(n^2) 로 표시한다

 

대표적인 빅-오

 

- O(logn)

- O(n)

- O(nlogn)

- O(n^2) -> 이중 for문

- O(n^3) -> 삼중 for문

 

O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) 

최고 <-----------------------------------------> 최악