Ray`s Tech Lab

누군가 x의 y승은 얼마인가? 라고 물었다. 그에 대한 대답은?

그냥 x ** y를 리턴하면 되긴 하지만(Python 기준), 그거 말고.

일반적으로는 다음과 같이 구할 수 있다.

def pow(x, y):
    answer = 1
    for i in range(y):       
    	answer *= x
    return answer

이 방법의 시간복잡도는 O(y)이다.

근데 더 빠르게 구할 순 없을까?

첨에는 단순하게, 저 방법은 루프를 y번 돌면서 하는거니까 루프횟수를 줄이면 된다고 생각했다.

만약 x의 y승을 구할 때 y가 짝수라면

x의 y승 = (x의 y/2승) * (x의 y/2승)

이고, y가 홀수라면

x의 y승 = (x의 y/2승) * (x의 y/2승) * (x)

이므로, 루프를 y번까지 돌 필요없이 y의 반 정도까지만 돌면 된다!고 생각해서 다음과 같이 코드를 짰었다.

def pow(x, y):
    answer = 1
    for i in range(y//2):
        answer *= i
    if y%2 == 0:                     # y가 짝수
        return answer * answer
    else:                            # y가 홀수
    	return answer * answer * 1

그러나 이것의 시간복잡도도 O(y)이다. y가 커질수록 y의 반까지만 루프를 돈다는 건 의미가 없어지기 때문..

그러나 이것의 시간복잡도를 O(lg y)로 줄일 수 있는 방법이 있다.

우선 거듭제곱을 구할 때 루프가 아니라 재귀로도 구할 수 있다는 점에 힌트가 있다.

다음과 같이 코드를 짜면 재귀의 방법으로 거듭제곱을 구할 수 있다.

def pow(x, y):
    if y == 0:
        return 1
    return x * pow(x, y - 1)

물론 저것의 시간복잡도 역시 아직은 O(y)임.

그러나 예를 들어서, 2의 8승은 다음과 같은 과정으로 구할 수 있다는 점에 주목하자.

2의 8승 = (2의 4승) * (2의 4승)

2의 8승 = ((2의 2승) * (2의 2승)) * ((2의 2승) * (2의 2승))

.....

즉 다음과 같이 가능하다는 말.

def pow(x, y):       
    if y == 1:
        return 1
    return pow(x, y//2) * pow(x, y//2)    # 물론 y가 짝수일 때만 가능

근데 같은 내용에 대해 재귀를 두 번 호출할 필요는 없으니, 다음과 같이 하는게 더 빠르다.

def pow(x, y):       
    if y == 1:
        return 1
    sub_answer = pow(x, y//2)
    return sub_answer * sub_answer    # 물론 y가 짝수일 때만 가능

아까 x의 y승을 구할 때 y가 홀수라면 x의 y승 = x의 y/2승 * x의 y/2승 * x라고 했었으니, y가 홀수일 때도 포함해 다음과 같이 완성 가능하다.

def pow(x, y):       
    if y == 1:
        return 1
    sub_answer = pow(x, y//2)
    
    if y%2 == 0:
    	return sub_answer * sub_answer    
    else:
        return sub_answer * sub_answer * x

이렇게 하면 O(lg y)의 시간복잡도로 거듭제곱을 더 빠르게 계산할 수 있다.

내가 한 거랑 뭐가 달랐던 걸까?

우선 기본적인 접근법은 같았던 것 같다. y가 짝수인지 아닌지에 따라, 2/y까지만 곱한 걸 다루는 면에서.

그러나 y가 만약 16으로 주어졌을 때, x의 16승은 x의 8승 * x의 8승이 맞긴 하지만 x의 8승을 구하는 것도 다시 반으로 쪼개서 할 수 있다는 점을 간과했다.