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

74

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

이렇게 매우 큰 수들은 일반적으로 [그림

2

-

8

]과 같이 시각화한다.

x

축은 해결할 문제 인스턴

스 크기를 나타내며

y

축은 알고리즘별 총 예상 런타임 성능을 나타낸다. 알고리즘의 복잡도가

증가함에 따라 ‘합리적인 시간’에 해결이 가능한 문제 인스턴스의 크기는 감소한다.

다음과 같이 복잡한 시나리오를 고려해보자.

●

누군가가 알고리즘을

O

(

N

2

+

N

)으로 분류한다면 당신의 응답은 무엇인가? [그림

2

-

7

]의 우세 계층에

서

N

2

이

N

보다 복잡도가 높으므로

O

(

N

2

+

N

)은

O

(

N

2

)으로 단순화할 수 있다. 비슷하게,

O

(

2

N

+

N

8

)은

O

(

2

N

)으로 단순화할 수 있다.

●

알고리즘이

O

(

50

×

N

3

)으로 분류된다면, 상수의 곱셈은 제거할 수 있으므로

O

(

N

3

)으로 단순화할 수

있다.

●

알고리즘의 동작이 때로는 문제 인스턴스 크기

N

보다 다른 속성에 더 의존적일 수 있다. 예를 들어, 숫

자 값

N

개를 런타임 성능이

N

에 정비례하는 핵심 작업으로 처리하는 알고리즘을 고려하자. 이 알고리즘

이 문제 인스턴스 내 모든 짝숫값을 처리하는 하위 작업을 가진다고 가정하자. 해당 하위 작업의 런타임

성능은

E

2

(여기서

E

는 짝숫값 개수 )에 정비례한다. 당신은 아마 알고리즘의 런타임 성능을

O

(

N

+

E

2

)으

로 지정하고 싶을 것이다. 예를 들어, 만약 입력 세트에서 모든 짝숫값을 제거할 수 있다면 성능을

O

(

N

)

으로 평가할 수 있으며, 이는 주목할 만하다.

E

≤

N

이므로 모든 숫자가 짝수인 최악의 경우 알고리즘의 ...