Page 16 -

그 림 1- 2 O ( f(n )) 비 교
1 0,0 0 0
8,0 0 0 1

6,0 0 0 주
2 0 n + 1 0 0 0 가
4,0 0 0 n 2 스
팬
2,0 0 0
0
0 2 0 4 0 6 0 8 0 1 0 0

3
2
빅 오 표 기 법 은 함 수 를 단 순 화 한 다. 예 들 들 어, f(n ) = 3 n + 5 n + 2 n + 1 0 0 0 과 같 은 함 수 가 있
3
3
다 면 단 순 화 한 결 과 일 때 O ( f(n )) = n 이 된 다. 이 는 0 ≤ f(n ) ≤ c n 을 만 족 하 는 값 c 를 항 상
구 할 수 있 기 때 문 이 다. 일 반 적 으 로 항 이 많 은 다 항 함 수 가 있 을 때 가 장 높 은 차 수 의 항 이 함
수 값 의 증 가 를 지 배 하 게 되 므 로 빅 오 표 기 법 으 로 단 순 화 할 때 는 가 장 적 은 항 을 취 한 다. 그 래 서
k
O (a 1 n + a 2 n k -1 + … + a n n + b ) = O (n ) 이 된 다.
k
앞 서 서 술 한 방 식 의 알 고 리 즘 실 행 시 간 을 알 고 리 즘 의 계 산 복 잡 도 (c o m p ut ati o n al c o m pl e xit y ), 짧 게
는 복 잡 도 (c o m pl e xit y )라 고 한 다. 알 고 리 즘 의 실 행 시 간 을 연 구 할 때 단 순 화 한 형 태 의 함 수 를 사 용

함 에 따 라 대 부 분 알 고 리 즘 의 실 행 시 간 은 몇 몇 단 순 화 한 함 수 중 하 나 가 된 다. 즉, 알 고 리 즘 의 복
잡 도 는 몇 가 지 공 통 범 주 나 계 열 의 하 나 에 속 한 다.

먼 저 상 수 함 수 (c o nst a nt f u n cti o n) f(n ) = c 가 있 다. 이 는 단 순 히 n 의 값 과 관 계 없 이 함 수 가 언 제 나
3
같 은 값 c 를 갖 는 다 는 것 을 뜻 한 다. c 가 터 무 니 없 이 큰 값 이 아 니 라 면 알 고 리 즘 에 서 기 대 할 수 있
는 가 장 좋 은 성 능 이 다. 빅 오 표 기 법 관 점 에 서 정 의 에 따 라 0 ≤ f(n ) ≤ c g (n ) = c · 1 인 양 의 상
= 1 이 다. 따 라 서 O (c ) = O (1 ) 이 된 다.
수 c 와 n 0 가 존 재 한 다. 실 제 로 c 는 함 수 의 상 수 값 이 고 n 0
이 와 같 은 방 식 으 로 작 동 하 는 알 고 리 즘 을 상 수 시 간 (c o nst a nt ti m e) 알 고 리 즘 이 라 하 는 데, 실 제 로 는
부 적 절 한 명 칭 이 다. 왜 냐 하 면 알 고 리 즘 이 입 력 과 관 계 없 이 항 상 같 은 시 간 걸 린 다 는 것 을 의 미 하
지 않 기 때 문 이 다. 이 것 은 알 고 리 즘 실 행 시 간 의 상 한 이 입 력 과 무 관 하 다 는 것 을 의 미 한 다. 예 를
들 어, x 가 양 수( x > 0 ) 일 때 x 값 에 y 값 을 더 하 는 단 순 한 알 고 리 즘 은 실 행 하 는 데 항 상 같 은 시 간

이 걸 리 지 않 는 다. x 가 양 수 면 덧 셈 을 수 행 하 고 그 렇 지 않 으 면 아 무 것 도 하 지 않 기 때 문 이 다. 상
한 이 덧 셈 에 걸 리 는 시 간 이 므 로 상 수 가 되 어 O (1 ) 계 열 에 속 한 다. 불 행 하 게 도 상 수 시 간 에 실 행
되 는 알 고 리 즘 은 많 지 않 다. 상 수 시 간 에 실 행 되 는 가 장 일 반 적 인 연 산 은 배 열 의 원 소 에 접 근 하
는 것 으 로, 접 근 할 배 열 원 소 의 인 덱 스 와 독 립 적 으 로 상 수 시 간 걸 린 다. 구 체 적 으 로 n 개 의 원 소 로

3 역 주 알 고 리 즘 이 n 의 값 과 관 계 없 이 상 수 시 간 이 걸 린 다.

0 2 7

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