Page 32 -

안에서 항목을 찾아내는 프로그램을 꼽을 수 있는데, 이 프로그 표 4.1.2 일반적인 증가함수들
램은 다음 절에서 살펴보겠다([프로그램 4.2.3](binarysearch. 증가도 두 배 추정
py) 참조). 로그의 밑수는 성장도 관점에서 보면 중요하지 않으 설명 함수 증가치
므로(밑수가 상수이므로 두 배 추정할 때 제거된다), 이런 프로그 상수 1 1
램의 성장도는 log n으로 표현한다. 이따금 lg n(밑수 2, 이진 로
로그 log n 1
그)나 ln n(밑수 e, 자연로그)처럼 구체적으로 공식을 명시하는 4
선형 N 2
경우가 있는데, 이것은 컴퓨터 프로그램을 연구할 때 자연적으로
선형 로그 n log n 2
발생하는 숫자이기 때문이다. 예를 들어 n을 이진수로 표현할 때 2
의 비트 수는 반올림한 lg n, 이진 검색 트리를 분석할 때는 ln n 이차 n 4 알고리즘과 데이터 구조
으로 자연스럽게 표현된다(4.4절 참조). 삼차 n 3 8
지수 2 n 2 n
선형 함수 입력 데이터의 각 부분을 처리하는 데 일정한 시간이
걸리거나 for 루프를 하나만 사용하는 프로그램을 쉽게 접할 수 있다. 이런 프로그램의 증가도는 선
형이라고 하며, 실행 시간이 문제 크기에 정비례한다. 표준 입력 장치에서 읽은 숫자들의 평균을 구하
는 [프로그램 1.5.3](average.py)이 대표적인 사례이며, 1.4절에서 설명한 배열 안의 요소를 뒤섞는

프로그램도 마찬가지다. plotfilter.py(프로그램 1.5.5)와 같은 필터도 이 범주에 속하며, 3.2절에서
설명한 입력 픽셀마다 일정한 산술 연산을 수행하는 여러 이미지 필터도 여기에 속한다.

दр 선형 로그 함수 문제 크기 n에 대해 실행 시간
1024T 이 n log n에 비례하는 프로그램을 설명하기
ࢶഋ ۽Ӓ ࢶഋ
512T ૑ࣻ ࢖ର ੉ର 위해 이 책에서는 선형 로그(linearithmic)라는
용어를 사용한다. 여기에서도 로그의 밑수는
중요하지 않다. couponcollector.py(프로그
64T 램 1.4.2)의 증가도가 선형 로그에 해당하며,

대표적인 사례로는 합병 정렬(merge sort)이
있다([프로그램 4.2.6] 참조). 직관적으로는
8T
2차원적인 해결책으로 표현되지만 선형 로그
4T
증가도를 가진 효율적인 알고리즘으로 해결
2T
۽Ӓ 할 수 있는 중요한 문제들이 많이 있다. 합병
T
࢚ࣻ 정렬을 포함한 이런 문제들은 이차 증가도를

௼ӝ 1K 2K 4K 8K 1024K 가진 알고리즘으로 해결할 수 있는 문제보다
그림 4.1.6 증가도 더 큰 규모의 문제를 해결할 수 있으므로 실
무에서 아주 중요하게 다루어진다. 다음 절
에서는 선형 로그 증가도 알고리즘을 개발하는 일반적인 설계 기법을 설명하겠다.

2
이차 함수 실행 시간 증가도가 n 인 프로그램들은 전형적으로 내포된 for 루프를 가지고 있으며, n개
요소의 모든 쌍에 일정 연산을 수행한다. universe.py(프로그램 3.4.2)에 있는 강제 업데이트 이중

485