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

55

2

장

알고리즘 분석

모델의 본질적인 특성상

N

이 두 배가 될 때 수행 시간이 네 배 증가해야 하기 때문이다. 이와

같이 파이썬에서 보다 진보되고 효율적인 카라추바 곱셈 알고리즘을 사용하는 모델이

N

자리

정수 곱셈의 성능을 더 정확하게 예측한다.

[표

2

-

2

]와 [표

2

-

3

]에 사용한 접근은 좋은 시작이지만, 코드를 리뷰하지 않고 런타임 성능만

을 기반으로 하는 간접적인 방식인 만큼 제한이 있다. 이 책 전반에서 알고리즘 구현을 기술하

고, 코드 구조를 기반으로 알고리즘 성능을 모델링하는 데 적절한 공식을 식별할 것이다.

2.3

성능 클래스

정확히 같은 문제를 해결하는 여러 알고리즘이 있을 때, 때로는 단지 수학적 모델을 사용해 성

능을 분류함으로써 어느 것이 가장 효율적인지 알아낼 수 있다. 알고리즘은 종종 ‘복잡도는

O

(

N

2

)이다’ 혹은 ‘최악의 성능은

O

(

N

log

N

)이다’와 같은 말로 표현된다. 이 용어를 알아보기

위해 먼저 [그림

2

-

1

]를 보자. 알고리즘 분석에 관해 설명하는 책이나 온라인 리소스를 읽어봤

다면 그림을 본 적이 있을 것이다.

목표는 주어진 문제 인스턴스

N

에 대해

최악의 런타임 성능

을 예측하는 모델을 찾는 것이다. 수

학에서는 이것을

상한선

이라 한다. ‘알고리즘은 이보다 더 열심히 일하지 않을 것이다’라고 생

각하면 이해가 쉽다. 대응되는 ...