Big-O 표기법

Big-O 표기법

1. 최악의 입력에 대한 기본연산의 횟수를 정확히 세는 건 일반적으로 귀찮고 까다롭다.

 

2. 정확한 횟수보다는 입력의 크기 n이 커질 때, 수행시간의 증가하는 정도가 훨씬 중요하다.

3. 수행시간 함수 T(n)이 n에 관한 여러 항(term)의 합으로 표현된다면, 함수 값의
증가율이 가장 큰 항 하나로 간략히 표기하는 게 시간 분석을 간단하게 하는 데 큰
도움이 된다.

4. 예를 들어, T(n) = 2n + 5이면, 상수항보다는 n의 일차항이 T(n)의 값을 결정하게
되므로 상수항을 생략해도 큰 문제가 없다