Page 20 -

그 림 1- 3 상 이 한 복 잡 도 계 열
1 0 0
4
8 0
3 1
6 0
2 주
4 0 가
1 2 0 스
팬
0 0
2 0 4 0 6 0 8 0 1 0 0 0 2 0 4 0 6 0 8 0 1 0 0
( a) O (l gn ) ( b) O (n )
1 0,0 0 0
4 0 0
8,0 0 0
3 0 0
6,0 0 0
2 0 0
4,0 0 0
1 0 0
2,0 0 0
0 0
2 0 4 0 6 0 8 0 1 0 0 0 2 0 4 0 6 0 8 0 1 0 0
( c) O (n l gn ) ( d) O (n ) 2

4,0 0 0
4,0 0 0
3,0 0 0
3,0 0 0
2,0 0 0
2,0 0 0
1,0 0 0 1,0 0 0
0 0
0 2 4 6 8 1 0 1 2 0 1 2 3 4 5 6 7
n
( e) O ( 2 ) (f) O (n !)

n
실 제 로 O (2 ) 또 는 O (n !) 복 잡 도 가 거 의 발 생 하 지 않 게 하 려 면 유 명 한 ( 또 는 악 명 높 은) 외 판 원 문
제 (tr a v eli n g s al es m a n pr o bl e m )를 생 각 해 보 라. 이 문 제 에 서 외 판 원 은 많 은 도 시 를 여 행 해 야 하 며
각 도 시 는 한 번 씩 만 방 문 해 야 한 다. 모 든 도 시 는 다 른 모 든 도 시 와 직 접 연 결 된 다. 풀 어 야 할 문

제 는 외 판 원 이 가 능 한 짧 은 거 리 를 여 행 하 면 서 각 도 시 를 한 번 씩 만 방 문 해 야 한 다 는 것 이 다. 직
접 적 인 해 결 방 법 은 도 시 들 을 대 상 으 로 모 든 가 능 한 순 열 을 시 도 하 는 것 이 다. n 개 의 도 시 가 있 다
2
n
면 복 잡 도 는 O (n !) 이 된 다. O (n 2 ) 으 로 문 제 를 해 결 하 는 더 나 은 알 고 리 즘 이 있 지 만, 실 제 차 이
는 크 게 나 지 않 는 다. 그 렇 다 면 이 문 제( 그 리 고 비 슷 한 다 른 문 제 들) 를 어 떻 게 해 결 할 수 있 을 까 ?
명 확 한 답 을 줄 수 있 는 좋 은 알 고 리 즘 은 모 르 더 라 도 근 접 한 결 과 를 얻 을 수 있 는 좋 은 알 고 리 즘
을 찾 을 수 있 다.

0 3 1

리 얼 월 드 알 고 리 즘( 본 문) 최 종.i n d d 3 1 2 0 1 9 - 0 8 - 1 2 오 후 4: 2 7: 1 0