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

76

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

2.13

연습 문제

1.

[표

2

-

5

]의 각 코드 조각의 시간 복잡도를 평가하자.

표

2-5

분석할 코드 조각

코드-

1

for i in range(100):

for j in range(N):

for k in range(10000):

...

코드-

2

for i in range(N):

for j in range(N):

for k in range(100):

...

코드-

3

for i in range(0,N,2):

for j in range(0,N,2):

...

코드-

4

while N > 1:

...

N = N // 2

코드-

5

for i in range(2,N,3):

for j in range(3,N,2):

...

2.

이 장에서 설명한 기술을 이용해 [코드

2

-

6

]의

f4

함수가 반환하는

ct

의 값을 모델링하자.

코드

2-6

분석할 예제 함수

def f4(N):

ct = 1

while N >= 2:

ct = ct + 1

N = N ** 0.5

return ct

이 장에서 사용한 모델 중 어느 것도 정확하지 않을 것이다. 대신에 밑수가

2

인

a

×

log

(

log

(

N

))을 기반으로 모델을 개발해보자.

N

=

2

50

까지 모델과 실제 결과를 비교하는

표를 구성하자. 이 동작의 알고리즘은

O

(

log

(

log

(

N

))으로 분류할 수 있을 것이다.

77

2