[알고리즘] 분할정복으로 O(logN) power구현

1번은 재귀 분할정복이고 2번은 반복문 분할 정복이다.

 

1번 

def power(n, p):
    if p == 0:
        return 1
    # Call this only once, instead of two times.
    power_p_divided_by_2 = power(n, p // 2)
    if p % 2:
        return n * power_p_divided_by_2 * power_p_divided_by_2
    else:
        return power_p_divided_by_2 * power_p_divided_by_2

2번

def power(a, n):
    ret = 1
    while n > 0:
        if n % 2 != 0:
            ret *= a
        a *= a
        n //= 2        
    
    return ret