더북(TheBook)

21.1 증가 기준

두 알고리즘을 분석해서 입력 크기로 실행 시간을 표현한다고 해보자. 알고리즘 A는 크기가 n인 문제를 해결하는 데 100n+1 단계가 필요하고, 알고리즘 Bn2+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

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.