Page 15 -

지 만, 연 산 수 를 알 고 리 즘 의 실 행 시 간 (r u n ni n g ti m e)이 라 고 한 다. 시 간 단 위 를 사 용 하 는 것 은 특 정
컴 퓨 터 모 델 과 관 계 된 실 행 시 간 추 정 일 수 있 으 므 로 유 용 하 지 않 다 고 본 다.

기 간 n 동 안 의 주 가 스 팬 을 구 하 는 데 걸 리 는 시 간 을 살 펴 보 자. 알 고 리 즘 은 2 행 에 서 시 작 하 여 주
가 (q u ot e )마 다 한 번 씩 n 번 을 수 행 하 는 루 프 로 구 성 된 다. 그 리 고 이 외 부 루 프 가 반 복 될 때 마 다 각

주 가 스 팬 을 찾 는 내 부 루 프 가 있 다. 각 주 가 에 대 해 이 전 모 든 주 가 와 해 당 주 가 를 비 교 하 는 데,
최 악 의 경 우 해 당 주 가 가 최 고 가 라 면 이 전 모 든 주 가 를 조 사 하 게 된 다. 주 가 k 가 이 전 모 든 주 가
가 운 데 가 장 높 다 면 내 부 루 프 는 k 번 실 행 된 다. 따 라 서 최 악 의 경 우, 주 가 가 오 름 차 순 으 로 되 어
있 다 면 7 행 은 다 음 횟 수 만 큼 실 행 된 다.

n n ( 1 )
2
1  n
2
이 식 은 숫 자 1 , 2 , … , n 을 다 음 과 같 이 두 번 더 해 보 면 쉽 게 이 해 할 수 있 다.
...
1 + 2 + + n
+ n + n - 1 + ... + 1
n + 1 + n + 1 + ... + n + 1 = n (n + 1)

6 행 은 알 고 리 즘 이 대 부 분 시 간 동 안 실 행 하 는 연 산 이 므 로 ( n (n + 1 ))/2 은 최 악 의 경 우 일 때 알 고
리 즘 의 실 행 시 간 이 된 다.

알 고 리 즘 의 실 행 시 간 을 이 야 기 할 때 실 제 관 심 은 입 력 데 이 터 n 이 클 때 의 실 행 시 간 이 다. 즉,
입 력 데 이 터 가 무 한 히 증 가 할 때 알 고 리 즘 이 어 떻 게 작 동 하 는 가 를 다 루 는 점 근 적 실 행 시 간
(as y m pt oti c r u n ni n g ti m e)이 실 제 관 심 대 상 이 다. 알 고 리 즘 의 점 근 적 실 행 시 간 은 특 별 한 표 기 법
을 사 용 하 여 표 현 한 다. 어 떤 양 의 초 깃 값 보 다 큰 모 든 n 에 대 해 임 의 의 함 수 f(n ) 이 또 다 른 함 수

g (n ) 을 양 의 상 수 c 로 스 케 일 링 한 c g (n ) 보 다 작 거 나 같 을 때 O ( f(n )) = g (n ) 이 라 고 한 다. 좀 더 정
가 있 으 면 O ( f(n )) = g (n ) 이
확 히 말 해, 모 든 n ≥ n 0 에 대 해 0 ≤ f(n ) ≤ c g (n ) 인 양 의 상 수 c 와 n 0
라 고 한 다.

여 기 서 O (f(n )) 을 빅 오 표 기 법(bi g O n ot ati o n )이 라 고 부 르 는 데, 아 주 큰 입 력 값 이 알 고 리 즘 의 성
능 차 이 를 측 정 할 수 있 는 핵 심 이 되 기 때 문 에 입 력 데 이 터 중 에 서 큰 값 이 관 심 대 상 이 된 다. 그
2
(n ) = n 이 라 는 두 함 수 가 있 다. 그 림 에 서 n 값 이 작 을 때
림 1 -2 를 보 면 f 1 (n ) = 2 0 n + 1 0 0 0 과 f 2
2
(n ) 이 크 지 만, 초 반 이 후 로 상 황 이 급 격 하 게 변 화 하 며 n 이 아 주 빠 르 게 증 가 하 는 것 을 볼 수
는 f 1
있 다.

0 2 6

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