Page 17 -

구 성 된 배 열 A 의 첫 번 째 원 소 A [0 ] 에 접 근 하 는 데 걸 리 는 시 간 과 마 지 막 원 소 A [n - 1 ] 에 접 근 하
는 데 걸 리 는 시 간 은 같 다.

상 수 시 간 알 고 리 즘 에 이 어 로 그 시 간 (l o g arit h mi c ti m e)으 로 실 행 되 는 알 고 리 즘 이 있 다. 로 그 함 수
y
(n ) 이 면 n = a 이 다.
또 는 로 그 는 l o g a (n ) 이 며, n 은 a 를 거 듭 제 곱 한 값 으 로 정 의 된 다. 즉, y = l o g a
이 때 a 는 로 그 의 밑 이 된 다. 로 그 의 정 의 에 서 x = a l o g a x 가 되 며, 이 는 로 그 가 숫 자 를 지 수 만 큼 거
듭 제 곱 한 것 의 역 임 을 보 여 준 다. 실 제 로 밑 을 3 으 로 하 는 로 그 2 7 의 값 은 3 이 며( l o g 3 2 7 = 3 ), 3 의
3
3 승 은 2 7 (3 = 2 7 ) 이 다. a 가 1 0 (a = 1 0 ) 이 면 밑 이 1 0 인 로 그 고, y = l o g(n ) 으 로 표 기 한 다. 컴 퓨
터 에 서 는 밑 이 2 인 로 그 를 많 이 사 용 하 는 데, 이 를 이 진 로 그 (bi n ar y l o g arit h m)라 고 하 며 특 수 표 기

(n ) 으 로 표 기 한 다. 이 는 밑 이 e (e ≈ 2 .7 1 8 2 8 ) 인 자 연 로 그(n at ur al l o g arit h m)와
법 으 로 l g(n ) = l o g 2
(n ) 으 로 표 기 한 다.
는 다 른 데, 자 연 로 그 는 특 수 표 기 법 인 l n(n ) = l o g e

Note 잠 깐 샛 길 로 빠 져 서 e 의 유 래 를 살 펴 보 자. e 는 1 8세 기 스 위 스 수 학 자 레 온 하 르 트 오 일 러( L e o n h ar d
E ul er ) 의 이 름 을 따 오 일 러 수(E ul er ’s n u m b er ) 라 고 종 종 불 리 는 데, 다 른 많 은 분 야 에 서 도 유 래 했 다. e는 식 ( 1 + 1 /
n
n ) 에 서 n 값 이 무 한 대 로 접 근 했 을 때 의 극 한 식 으 로 표 현 된 다. 오 일 러 의 이 름 을 따 기 는 했 지 만, 실 제 로 는 1 7세 기 스
위 스 의 수 학 자 야 코 프 베 르 누 이( J a c o b B er n o ulli ) 가 연 속 적 으 로 적 용 되 는 이 자( 복 리) 를 계 산 하 는 공 식 을 찾 아 내 는
과 정 에 서 발 견 했 다.
R % 의 이 자 를 주 는 은 행 에 d 달 러 를 예 금 한 다 고 해 보 자. 이 자 를 1년 에 한 번 계 산 한 다 면 1년 후 예 금 한 돈 은 d +
d (R /1 0 0) 만 큼 된 다. r을 R /1 0 0 이 라 고 설 정 하 면 돈 은 d ( 1 + r)가 된 다. 따 라 서 R = 5 0 , r = 1 /2 일 때 예 금 한 돈 이 1. 5
× d 로 증 가 함 을 검 증 할 수 있 다. 이 자 를 1년 에 2 번 계 산 한 다 면 6 개 월 주 기 로 이 자 는 r/2 이 되 고, 6 개 월 후 예 금 한 돈
은 d ( 1 + r/2) 가 된 다. 그 리 고 또 6 개 월 후, 즉 1년 뒤 에 는 d ( 1 + r/2)( 1 + r/2) = d ( 1 + r/2) 이 된 다. 산 술 식 을 적 용
2
하 여 이 자 를 매 년 n 번 적 용 한 다 면 1년 후 에 는 d ( 1 + r/n ) 이 된 다. R = 1 0 0 % 인 경 우 r = 1 이 되 고, 계 속 해 서 더 짧
n
n
은 간 격 으 로 증 가 시 키 면 n 은 무 한 대 로 가 게 된 다. 이 때 d = 1 이 면 1년 이 되 었 을 때 예 금 한 돈 은 ( 1 + 1 /n ) = e로 늘
어 나 게 된 다.

(a ) 이 기 때 문 에 밑 이 다 른 로 그 는 상 수 승 수 에 따 라 다
로 그 의 기 본 특 성 은 l o g a (n ) = l o g b (n )/l o g b
(2 ) 이 다. 그 러 므 로 더 구 체 적 인 O (l g(n )) 역 시 많
르 다 는 것 이 다. 예 를 들 어, l g(n ) = l o g 1 0 (n )/l o g 1 0
이 사 용 하 지 만, 통 상 O (l o g(n )) 로 나 타 내 는 같 은 복 잡 도 계 열 로 모 든 로 그 함 수 를 묶 는 다. 어 떤 것
을 반 복 해 서 2 로 나 눈 다 면 본 질 적 으 로 거 기 에 로 그 함 수 를 적 용 하 기 때 문 에 문 제 를 반 복 해 서 2 로

나 누 어 풀 면 O (l g(n )) 의 복 잡 도 를 갖 는 알 고 리 즘 이 만 들 어 진 다. 중 요 한 로 그 시 간 복 잡 도 의 알 고
리 즘 은 탐 색 과 관 련 된 알 고 리 즘 이 며, 가 장 빠 른 탐 색 알 고 리 즘 은 밑 이 2 인 로 그 시 간 복 잡 도 로 수
행 된 다.

로 그 시 간 알 고 리 즘 보 다 더 많 은 시 간 이 소 요 되 는 알 고 리 즘 은 f(n ) = n , 즉 입 력 에 비 례 하 여 실 행
시 간 이 걸 리 는 선 형 시 간 (li n e ar ti m e) 알 고 리 즘 이 다. 이 알 고 리 즘 의 복 잡 도 는 O (n ) 이 다. 이 알 고 리

0 2 8

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