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

57

2

장

알고리즘 분석

른 곱셈 알고리즘의 구조가 수행 방식을 결정하기 때문이다. 어떤 슈퍼컴퓨터도 카라추바 구현

이 갑자기 선형

TL

(

N

)으로 모델링된 방식으로 동작하도록 만들지 않는다.

다음 절에서는 점근적 분석을 알아본다. 이는 알고리즘 성능을 평가할 때 실제 컴퓨터에 관한

정보를 제외할 수 있는 접근 방식이다. 고성능 컴퓨터는 코드를 더 빠르게 실행할 수 있지만 점

근적 분석의 법칙을 바꾸지는 못한다.

2.4

점근적 분석

덧셈 상수

개념은 앞서 논의한 속도계를 비롯한 많은 실생활 시나리오에서 흔히 사용된다. 예를

들어 ‘

40

분 뒤에 도착할 건데

5

분 정도 빠르거나 늦을 수도 있어’라고 말할 때를 의미한다.

점근적 분석

asymptotic

analysis

은 이런 아이디어를 더 발전시키고, 알고리즘을 분석하기 위해

곱셈

상수

개념을 도입한다.

무어의 법칙

Moore

’

s

Law

을 들어봤다면 이 개념이 익숙할 것이다. 인텔의

CEO

이자 공동 창립자인 고든 무어는

1965

년에, 집적회로 한 개당 컴포넌트의 개수가

10

년간

매년 두 배가 될 것이라고 예측했다. 그리고

1975

년에는 이 예측을 매년에서 매

2

년으로 수정

했다. 예측은 거의

40

년 동안 유효했으며, 컴퓨터의 속도가 기본적으로 매

2

년마다 두 배로 늘

어나는 이유를 설명해준다. 곱셈 상수를 컴퓨팅에 적용해보면, 구형 컴퓨터는 최신 컴퓨터와

동일한 프로그램을 실행할 때

1

,

000

배 혹은 그 이상 느릴 수 있다.

같은 문제를 해결하는 두 알고리즘을 고려해보자. 앞서 소개한 기술을