Big-O 표기법

두 알고리즘 A와 B 를 비교하려면?

 

1. Ark B 보다 조금, 많이 빨라요 -> 애매모호
2. 프로그램을 짜서 실행 속도 비교 -> 환경에 의존적
3. 입력이 적은 구간과 많은 구간에서 성능이 확연하게 차이날 경우는?

 

대안으로 Big-O 표기법 사용

 

1단계: 대략적인계산

• 수행되는 연산의 개수를 대략적으로 판단

2단계:대장만 남긴다

• 규칙1) 영향력이 가장 큰 대표 항목만 남기고 삭제
• 규칙2) 상수 무시(ex. 2n =>n)