알고리즘 분류

  • 분할 정복 (Divide and Quanquer)

점화식

a

알고리즘 유도

$2^{17}$을 점화식1의 정의에 따라 이진 트리로 나타내보자.

https://i.ibb.co/3Tkq3Sd/001.jpg

점화식대로라면 하위 문제를 전부 풀어야할거 같지만 그렇지 않다.

https://i.ibb.co/xhy1K9f/002.jpg

이 문제는 중복 문제가 존재하기 때문에 동적 계획법으로 풀어도 된다.

그러나 같은 레벨에 존재하는 문제들이 모두 같은 문제이기 때문에,

오른쪽 서브 트리는 사실 계산하지 않아도 된다.

트리의 구조상 memoization을 사용하면 오히려 낭비가 될 수 있다.

https://i.ibb.co/26c2PfS/003.jpg

$n$번 수행해야하는 연산이 약 $log_2{n}$번 정도로 감소한 것을 알 수 있다.

소스코드

방법1. 재귀 함수

1
2
3
4
5
6
7
8
9
10
11
12
def fast_power(a, x):
    if x == 0:
        return 1
    elif x == 1:
        return a

    y = fast_power(a, x >> 1)  # 좌측 서브트리만 계산하면 된다.

    if x & 1:
        return y * y * a
    else:
        return y * y

위에서 정의한 그대로 풀어나가는 방법이다.

n // 2 와 n >> 1 은 같다. (후자가 더 빠른 방법)

방법2. 반복문

1
2
3
4
5
6
7
8
9
10
11
12
13
def fast_power(a, x):
    if x == 0:
        return 1
    elif x == 1:
        return a
    else:
        r = 1
        while x:
            if x & 1:
                r *= a
            a *= a
            x >>= 1
    return r

https://i.ibb.co/1LmsySx/004.jpg

결국 레벨이 진행되다보면 $x = 1$에서 $f(?,0)$꼴이 나오는데,

이것들은 모두 1로 소거되고, 결국 남는 것은 이미 평가된 거듭제곱들의 곱이다.

만약 어떤 레벨 $i (i>=1)$의 $x$ 값이 홀수라면,

그 레벨에서 곱해지는 거듭제곱의 기대 값은 $2^{2^{i-1}}$이다.

이 값을 만들기 위해 각 레벨마다 밑($a$)의 곱을 누적하였다가,

홀수 레벨을 만나면 $r$에 곱한다.

파이썬 pow보다 빠른가?

벤치마크 (fast pow, python pow, **)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
start_time = time.time()

for i in range(10000):
    fast_power(2, i)

end_time = time.time()

print(f'My FastPow: {end_time - start_time} sec')

start_time = time.time()

for i in range(10000):
    pow(2, i)

end_time = time.time()

print(f'Python Pow: {end_time - start_time} sec')

start_time = time.time()

for i in range(10000):
    2 ** i

end_time = time.time()

print(f'** Pow: {end_time - start_time} sec')

1
2
3
My FastPow: 0.09695100784301758 sec
Python Pow: 0.07985901832580566 sec
** Pow: 0.0790097713470459 sec

파이썬의 pow가 내장 함수이다보니 훨씬 최적화가 더 잘 된 느낌이다.

파이썬 성능 향상을 위해서는 내장 함수를 잘 알아야겠다.