똑똑한 코드 작성을 위한 실전 알고리즘

53

2

장

알고리즘 분석

선형 모델

TL

은 총 시간을 과소평가하고 이차 모델

TQ

는 과대평가한다.

N

=

10

,

000

,

000

일 때

TL

은

5

,

957

초(약

10

분)가 걸린다고 선언하고

TQ

는

326

,

300

초(약

91

시간 )가 걸린다고 선언

한다.

TN

은 실제 성능이

9

,

879

초(

2

.

75

시간 )일 때

10

,

421

초(약

2

.

9

시간 )로 추정하므로 성능

을 더 잘 예측한다.

다행히 프로토타입은 밤새 처리를 완료할 수 있지만, 프로토타입에 도입한 자료구조와 알고리

즘을 확인해야만 문제 인스턴스에 관계없이 결과를 보장할 수 있다.

공식

a

×

N

×

log

(

N

)이 동작을 잘 모델링하는 이유는 무엇일까? 이는 프로토타입 애플리케이

션 내에서 사용한 기본 알고리즘과 관련이 있다. 앞서 살펴본 선형 모델, 이차 모델,

N

log

N

이

알고리즘을 분석하는 데 일반적으로 사용된다. 약

50

년 전에 발견된 놀라운 결과를 보여주는

예제 하나를 더 보도록 하자.

2

2.2

곱셈 성능 예측하기

[코드

2

-

2

]에 있는 두 가지 예시를 보자. 초등학교에서 배운 알고리즘을 사용해 두

N

자리 정

수를 곱한다. 해당 알고리즘을 정확하게 정의하지는 않겠지만 최종 답을 계산하기 위해 합산된

원래 숫자 아래에 나열된

N

개의 곱을 생성함을 볼 수 있다.

코드

2-2

초등학교 알고리즘을 사용해 두

N

자리 정수 곱하기

456 ...