21.1 증가 기준
두 알고리즘을 분석해서 입력 크기로 실행 시간을 표현한다고 해보자. 알고리즘 A는 크기가 n인 문제를 해결하는 데 100n+1 단계가 필요하고, 알고리즘 B는 n2+n+1 단계가 필요하다.
다음 표는 문제 크기에 따라 이들 알고리즘의 실행 시간을 나타낸 것이다.
입력 크기 |
알고리즘 A의 실행 시간 |
알고리즘 B의 실행 시간 |
10 |
1 001 |
111 |
100 |
10 001 |
10 101 |
1 000 |
100 001 |
1 001 001 |
10 000 |
1 000 001 |
> 1010 |