2021-11-20 O(n)을 O(logn)으로 바꾸기

 

 

logN의 시간복잡도를 가지려면 문제의 크기가 절반씩 줄어들어야 한다. 

그렇다면 문제의 크기를 절반 씩 줄이는 것에 목표를 두자.

 

power(3,5)라면, power(3,2) * power(3,2) * power(3,1) -> power(3,1)*power(3,1)*power(3,1)*power(3,1)*power(3,1)

원래라면 5의 시간복잡도가 3이 됐다.

 

즉 y값에 따라서 문제의 크기를 절반씩 줄여주면 된다.

 

 

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

 

 

2021-11-20