Page 18 -

즘 은 답 을 찾 기 위 해 전 체 입 력 데 이 터 를 스 캔 해 야 할 수 도 있 다. 예 를 들 어, 정 렬 되 지 않 은 임 의
의 아 이 템 집 합 을 탐 색 한 다 면 원 하 는 것 을 찾 기 위 해 모 든 아 이 템 을 거 쳐 야 할 수 도 있 으 므 로 선

형 시 간 에 실 행 된 다. 1
선 형 시 간 보 다 느 린 것 은 로 그 선 형 시 간 (l o g- li n e ar ti m e) 알 고 리 즘 인 데, f(n ) = n l o g(n ) 이 므 로 주
가
스
O (n l o g(n )) 라 고 쓴 다. 앞 에 서 처 럼 실 제 로 는 밑 이 2 인 알 고 리 즘 이 보 편 적 이 지 만, 로 그 는 어 느 밑 팬
이 나 취 할 수 있 다. 이 러 한 알 고 리 즘 은 선 형 시 간 알 고 리 즘 과 로 그 시 간 알 고 리 즘 의 결 합 으 로, 문
제 를 반 복 적 으 로 나 누 고 나 눈 각 부 분 에 선 형 시 간 알 고 리 즘 을 적 용 한 다. 좋 은 정 렬 알 고 리 즘 은
로 그 선 형 시 간 복 잡 도 를 갖 는 다.

k
알 고 리 즘 의 실 행 시 간 이 다 항 함 수 f(n ) = (a 1 n + a 2 n k -1 + … + a n n + b ) 일 때 앞 에 서 보 았 듯 이
k
O (n ) 의 복 잡 도 를 가 지 는 데, 이 때 알 고 리 즘 을 다 항 시 간 (p ol y n o mi al ti m e) 알 고 리 즘 이 라 고 한 다. 많
2
은 알 고 리 즘 이 다 항 시 간 에 실 행 된 다. 중 요 알 고 리 즘 계 열 은 O (n ) 시 간 에 실 행 되 는 알 고 리 즘 으
로, 이 를 따 로 이 차 시 간 (q u a dr ati c ti m e) 알 고 리 즘 이 라 고 부 른 다. 일 부 비 효 율 적 인 정 렬 방 법 은 이
차 시 간 에 실 행 되 는 데, 이 는 각 각 n 자 릿 수 인 두 수 를 곱 하 는 보 편 적 방 법 과 동 일 하 게 작 동 한 다.
실 제 로 는 숫 자 를 곱 하 는 더 효 율 적 인 방 법 이 있 으 며, 고 성 능 산 술 연 산 이 필 요 한 응 용 프 로 그 램 에

서 이 러 한 방 법 을 사 용 한 다.
n
다 항 시 간 알 고 리 즘 보 다 느 린 것 은 지 수 시 간 (e x p o n e nti al ti m e) 알 고 리 즘 으 로, f(n ) = c 이 된 다. 여
n
c
n
기 서 c 는 상 수 이 며 복 잡 도 는 O (c ) 이 다. 이 때 n 과 c 의 차 이 점 을 분 명 히 해 야 한 다. n 과 지 수 의
위 치 를 바 꿨 지 만, 결 과 함 수 에 는 큰 차 이 가 있 다. 앞 서 말 했 듯 이, 거 듭 제 곱 (e x p o n e nti ati o n )은 로 그
함 수 의 역 이 며 단 순 히 상 수 를 가 변 숫 자 만 큼 거 듭 곱 한 것 이 다.

Note 거 듭 제 곱 은 c 이 다. 지 수 함 수( e x p o n e nti al f u n cti o n) 는 상 수 c가 e일 때( c = e), 즉 f(n ) = e 인 특 수 함
n
n
수 로, 여 기 서 e는 앞 에 서 살 펴 본 오 일 러 수 다. 거 듭 제 곱 은 n 개 의 입 력 이 각 각 c의 다 른 값 들 을 취 할 수 있 고 모 든 가 능
한 경 우 를 시 도 해 야 하 는 입 력 n 의 문 제 를 처 리 해 야 할 때 발 생 한 다. 첫 번 째 입 력 으 로 c개 의 값 을 가 지 며, 이 값 들 각
2
2
각 에 대 해 두 번 째 입 력 으 로 c개 값 을 가 지 면 경 우 의 수 는 c × c = c 이 된 다. 또 한, c 인 입 력 들 각 각 에 대 해 세 번 째
n
입 력 으 로 c개 의 가 능 한 값 을 가 지 면 c × c = c 이 된 다. 그 리 고 이 것 은 c 이 되 는 마 지 막 입 력 까 지 반 복 된 다.
2
3
지 수 시 간 알 고 리 즘 보 다 더 느 린 것 은 O (n !) 의 팩 토 리 얼 시 간 (f a ct ori al ti m e) 알 고 리 즘 이 다. 여 기 서
팩 토 리 얼 수 (f a ct ori al n u m b er )는 n ! = 1 × 2 × … × n 으 로 정 의 하 고, 0 ! = 1 로 정 의 한 다. 팩 토 리
얼 은 입 력 으 로 모 든 가 능 한 순 열 을 시 도 하 여 문 제 를 풀 고 자 할 때 작 용 한 다. 순 열 (p er m ut ati o n )은
일 련 의 값 들 을 서 로 다 른 순 서 로 배 열 하 는 것 을 말 한 다. 예 를 들 어, 값 [ 1 , 2 , 3 ] 이 있 을 때 [1 , 2 ,

3 ], [1 , 3 , 2 ], [2 , 1 , 3 ], [2 , 3 , 1 ], [3 , 1 , 2 ], [3 , 2 , 1 ] 의 순 열 을 갖 는 다. 첫 번 째 위 치 에 는 n 개 의

0 2 9

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