Page 29 -

수학적 분석 프로그램 실행 시간을 설명하는 커누스 교수의 수학적 모델 दп
의 기본적인 개념은 간단하다. 전체 실행 시간은 다음과 같은 두 가지 요 1024T
소에 의해 결정된다. 512T

• 각 문장을 실행하는 비용
• 각 문장을 실행하는 빈도
64T
여기서 첫 번째는 시스템의 속성, 두 번째는 알고리즘의 속성이다. 프로
그램의 모든 명령에 대해 이 두 가지 속성을 모두 알면 각 명령을 실행하
는 횟수를 곱해 모두 더함으로써 프로그램의 실행 시간을 구할 수 있다. 8T
4T
이때 가장 힘든 것은 문장의 실행 빈도를 결정하는 것이다. 어떤 문장
2T
은 간단히 결정할 수 있다. 예를 들어 threesum.countTriples() 안에서
T
count를 0으로 초기화하는 문장은 딱 한 번만 실행된다. 다른 문장은 조
금 더 깊이 생각해야 한다. 예를 들어 threesum.countTriples() 안에 있 ௼ӝ 1K 2K 4K 8K
는 if 조건문은 정확히 n(n - 1)(n - 2)/6번 실행된다(입력 배열에서 세 그림 4.1.3 로그-로그 그래프
개의 숫자를 고르는 경우의 수와 일치한다. [연습문제 4.1.5] 참조).

이와 같은 방식으로 빈도수를 분석하면 복잡하고 긴 수학 표현식이 만들어질 수 있다. 수학적 분석
에서 문제를 단순화하기 위해 다음과 같은 두 가지 간단한 근사식(approximate expressions)을 만든다.
첫째, 물결식(tilde notation)이라고 하는
import stdarray
import stdio
수학 장치를 이용해 수식의 최고차항
def writeTriples(a):
# 연습문제 4.1.1 참조 (leading term)을 이용한다. n이 커지면서
def countTriples(a): f(n)으로 나누면 1에 수렴하는 모든 값
n = len(a) 1
count = 0 을 ~f(n)으로 표기한다. 그리고 n이 커
for i in range(n):
for j in range(i+1, n): n 지면서 g(n)/f(n)이 1에 수렴하는 것을
2
ղࠗ
for k in range(j+1, n): ~n / 2 나타내기 위해 g(n)~f(n)으로 표기한다.
ܖ೐
3
if (a[i] + a[j] + a[k]) == 0: ~n / 6
count += 1 이 표기법을 이용할 때는 작은 값을 나
return count
타내는 복잡한 부분을 무시할 수 있다.
def main(): ੑ۱ ؘ੉ఠী ٮۄ ߄Շח ࠗ࠙
a = stdarray.readInt1D() 예를 들어 threesum.py에 있는 if 조건
count = countTriples(a)
3
stdio.writeln(count) 문은 ~n /6번 실행된다고 할 수 있다.
if count < 10:
2
writeTriples(a) n(n-1)(n-2)/6 = n /6 - n /2 + n/3
3
if __name__ == '__main__': main()
3
인데, 이 식을 n /6으로 나눌 때 n이 커
그림 4.1.4 프로그램 실행 빈도수 분석
지면서 이 식이 1에 수렴하기 때문이다.
이 표기법은 최고차항 이외의 항들의 중요성이 상대적으로 적을 때 유용하다. 예를 들어 앞의 식에서
3
2
n=1,000일 때, n /6 ≈ 166,666,667에 비해 - n /2 + n/3 ≈ -499.667의 중요성이 상대적으로 떨
어진다. 둘째, 우리는 가장 자주 실행되는 명령에 집중한다. 이 명령들은 종종 프로그램의 내부 루프
라고 한다. 이런 프로그램에서는 내부 루프 외부의 명령들이 실행하는 시간은 상대적으로 중요성이
떨어진다고 간주한다.
482