Page 19 -

가 능 한 값 이 있 고, 그 다 음 은 하 나 의 값 을 사 용 했 으 므 로 두 번 째 위 치 에 n - 1 개 의 값 이 올 수 있
다. 그 래 서 앞 의 두 위 치 에 대 해 n × (n - 1 ) 개 의 서 로 다 른 순 열 이 만 들 어 진 다. 이 처 럼 가 능 한 값

이 하 나 만 존 재 하 는 마 지 막 위 치 까 지 계 속 진 행 하 면 결 국 n × (n - 1 ) × … × 1 = n ! 을 갖 게 된
다. 이 와 같 은 방 법 으 로 계 승 수 는 순 서 를 뒤 섞 어 만 든 다. 예 를 들 어, 카 드 1 팩 의 모 든 가 능 한 뒤
섞 임 수 는 5 2 ! 이 되 는 데, 이 는 천 문 학 적 숫 자 다.

경 험 적 으 로 보 면 알 고 리 즘 은 다 항 시 간 복 잡 도 정 도 의 알 고 리 즘 이 좋 기 때 문 에 그 정 도 의 성 능 을
보 이 는 알 고 리 즘 을 찾 는 것 이 과 제 다. 그 러 나 불 행 히 도 모 든 유 형 의 중 요 문 제 에 대 해 다 항 시 간 알
고 리 즘 을 알 지 못 한 다. 표 1 -1 을 살 펴 보 면 어 떤 문 제 에 대 해 실 행 시 간 이 O (2 ) 인 알 고 리 즘 이 있 을
n
때 이 알 고 리 즘 은 입 력 이 아 주 작 은 값 들 로 구 성 된 쉬 운 문 제 를 제 외 하 고 는 거 의 쓸 모 가 없 다.

표 1- 1 함 수 의 증 가

함 수 입 력 크 기
1 1 0 1 0 0 1 0 0 0 1, 0 0 0, 0 0 0
l g(n ) 0 3. 3 2 6. 6 4 9. 9 7 1 9. 9 3
n 1 1 0 1 0 0 1 0 0 0 1, 0 0 0, 0 0 0
n l n(n ) 0 3 3. 2 2 6 6 4. 3 9 9 9 6 5. 7 8 1. 9 × 1 0 7

n 2 1 1 0 0 1 0, 0 0 0 1, 0 0 0, 0 0 0 1 0 1 2
n 3 1 1 0 0 0 1, 0 0 0, 0 0 0 1 0 9 1 0 1 8
2 n 2 1 0 2 4 1. 3 × 1 0 3 0 1 0 3 0 1 1 0 1 0 5. 5
n ! 1 3, 6 2 8, 8 0 0 9. 3 3 × 1 0 1 5 7 4 × 1 0 2 5 6 7 1 0 1 0 6. 7

n
그 림 1 -3 에 서 도 확 인 할 수 있 다. 가 장 아 랫 줄 의 그 래 프 를 보 면 O (2 ) 과 O (n !) 이 작 은 n 값 에 서 급
등 하 기 시 작 함 을 알 수 있 다.

그 림 1 -3 은 복 잡 도 함 수 의 그 래 프 를 선 으 로 보 여 준 다. 실 제 로 알 고 리 즘 을 연 구 할 때 n 은 자 연 수
라 서 선 대 신 점 으 로 산 포 도 가 나 타 난 다. 물 론 로 그 와 선 형, 로 그 선 형, 다 항 함 수 는 실 수 에 대 해
직 접 정 의 되 므 로 일 반 함 수 정 의 를 사 용 하 여 그 래 프 를 선 으 로 그 리 는 것 은 문 제 가 되 지 않 는 다.
a (1 /b )
거 듭 제 곱 의 해 석 은 통 상 적 으 로 정 수 에 대 한 것 이 지 만, x (a /b ) = ( x ) = x 이 므 로 유 리 수 를 지
a
b
x
l nb x
수 로 거 듭 제 곱 할 수 있 다. 그 다 음 실 수 를 지 수 로 하 는 거 듭 제 곱 은 b = (e ) = e 로 정 의 한 다.
xl nb
팩 토 리 얼 에 대 해 서 는 좀 더 고 급 수 학 에 서 모 든 실 수 에 대 해 정 의 할 수 있 다 는 것 이 밝 혀 졌 다( 음
의 팩 토 리 얼 은 무 한 으 로 간 주 한 다). 따 라 서 복 잡 도 함 수 를 선 으 로 그 리 는 것 이 정 당 화 된 다.

0 3 0

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