Page 33 -

루프는 이런 부류에 속하는 대표적인 사례로서, 삽입 정렬(프로그램 4.2.4)이라고 하는 기초적인 정
렬 알고리즘도 여기에 속한다.

삼차 함수 이번 절 예제인 threesum.py는 n개 요소에서 세 쌍을 모두 뽑아 처리하기 위해 삼중 for 루
3
프를 사용하기 때문에 실행 시간 증가도가 n 으로서 삼차 함수이다. 1.4절에서 구현한 행렬 곱셈의
3
실행 시간도 두 개의 m × m 행렬을 곱할 때 m 의 증가도를 가지고 있으므로 삼차 함수이지만, 입
2
력의 크기(행렬 요소의 수)가 n = m 에 비례하므로, 알고리즘의 시간 증가도가 삼차 함수라기보다는
3/2
n 라고 분류하는 편이 옳다.

지수 함수 2.3절에서 설명한 것처럼 towersofhanoi.py(프로그램 2.3.2)와 beckett.py(프로그램
n
2.3.3)는 둘 다 n개 요소의 모든 부분집합을 처리하기 때문에 실행 시간이 2 에 비례해 증가한다. 일
n
반적으로 ‘지수’라는 용어는 b>1인 모든 상수에 대한 b 증가도를 가진 알고리즘을 모두 의미하며, b
값에 따라 차이가 많이 발생하지만 중요하지 않다. 지수 함수는 아주 느리므로 문제가 클 때는 이런
프로그램을 실행하면 결코 안 된다. 지수 증가도를 가진 알고리즘이 최선의 해결책인 문제들이 아주
많이 있으므로 이런 문제는 알고리즘 이론에서 아주 중요한 역할을 담당한다.

표 4.1.3 일반적인 증가도 가설 정리
설명 증가도 예 형태

상수 1 count += 1 문장
(정숫값 증가)

로그 log n while n > 0: 절반으로 나눔
n = n // 2 (이진으로 표현할 때 필요
count += 1 한 비트 수)
선형 n for i in range(n): 단일 루프
if a[i] == 0:
count += 1

선형 로그 n log n [합병 정렬(프로그램 4.2.6) 참조] 분할 정복
(합병 정렬)

이차 n 2 for i in range(n): 이중 내포 루프
for j in range(i+1, n): (모든 쌍 확인)
if (a[i] + a[j]) == 0:
count += 1

삼차 n 3 for i in range(n): 삼중 내포 루프
for j in range(i+1, n): (모든 세 쌍 확인)
for k in range(j+1, n):
if (a[i] + a[j] + a[k]) == 0:
count += 1
지수 2 n [그레이 코드(프로그램 2.3.3) 참조] 철저한 검색
(모든 부분집합 검사)

486