[Algorithm] 알고리즘 별 시간 복잡도 비교해보기

문제 

[-7, 4, -3, 6, 3, -8, 3, 4]로 이루어진 1차원 배열이 있을 때 합이 최대인 부분 구간을 찾는 알고리즘을 만들어보도록 하겠다.

최대 합을 갖는 구간은 [4, -3, 6, 3]으로 합이 10이다.

---

※python 언어를 사용하여 구현함.

 

BruteForce 알고리즘  : O(N^2), O(N^3)

inefficient_max_sum()함수는 주어진 배열의 모든 부분 구간을 순회하면서 그 합을 계산하는 알고리즘이다.

이 알고리즘은 O(N^2)개의 후보 구간을 검색하고, 각 구간의 합을 구하는데 O(N)의 시간이 걸리기 때문에 이 함수의 총 알고리즘 시간 복잡도는 O(N^3)이 된다.

better_max_sum()함수는 위의 함수를 조금 변형하여서 O(N^2)의 시간 복잡도를 나타낸다.

def inefficient_max_sum(lst):
    N = len(lst)
    ret = float('-inf')
 
    for i in range(N):
        for j in range(i, N):
            lst_sum = sum(lst[i:j+1])
            ret = max(ret, lst_sum)
 
    return ret
 
 
def fast_max_sum(lst):
    N = len(lst)
    ret = float('-inf')
    
    for i in range(N):
        lst_sum = 0
        for j in range(i, N):
            lst_sum += lst[j]
            ret = max(ret, lst_sum)
 
    return ret
 
if __name__ == "__main__":
    lst = [-7, 4, -3, 6, 3, -8, 3, 4]
    print(inefficient_max_sum(lst))
    print(fast_max_sum(lst))
    
    # 10

 

---

 

분할 정복 알고리즘 : O(N log N)

입력받은 배열을 우선 절반으로 잘라 왼쪽과 오른쪽으로 나눈다. 이때 최대 합 구간은 두 배열 중 하나에 속해 있을 수도, 두 배열 사이에 걸쳐 있을 수도 있다. (아래 코드의 single 변수에 재귀함수를 이용해 두 배열 사이에 최대 구간을 값을 초기화한다.)

def fast_max_sum(lst, low, high):
    # 구간의 길이가 1인 경우
    if low == high: return lst[low]
 
    # 배열을 lst[low ~ mid], lst[mid+1 ~ high]로 나눈다.
    mid = (low + high) // 2
 
    left, right = float('-inf'), float('-inf')
 
    # lst[i ~ mid]의 최대 구간을 찾는다.
    lst_sum = 0
    for i in range(mid, low-1, -1):
        lst_sum += lst[i]
        left = max(left, lst_sum)
 
    # lst[i ~ mid]의 최대 구간을 찾는다.
    lst_sum = 0
    for j in range(mid+1, high+1, 1):
        lst_sum += lst[j]
        right = max(right, lst_sum)
    
    # 최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
    single = max(fast_max_sum(lst, low, mid), fast_max_sum(lst, mid+1, high))
 
    # 두 경우 중 최대치를 반환한다.
    return max(left, right, single)
 
if __name__ == "__main__":
    lst = [-7, 4, -3, 6, 3, -8, 3, 4]
    print(fast_max_sum(lst, 0, len(lst)-1))
 
    # 10

 

---

 

동적 계획법(DP) 알고리즘 : O(N)

lst[i]를 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수 max_at(i)가 있다. 그런데 lst[i]에서 끝나는 최대 합 부분 구간은 lst[i]하나로 이루어져 있거나 (원소가 하나인 배열) 또는 lst[i-1]을 오른쪽 끝으로 갖는 최대 합 부분 구간에 lst[i]를 붙인 형태로 구성되어 있을 것이다.

 

즉, lst[-1]까지의 부분 구간의 합을 매번 새로 구할 필요가 없다는 뜻이다. 이러한 max_at()를 다음과 같은 점화식으로 표현할 수 있게 된다.

 

max_at(i) = max(0, max_at(i-1)) + lst[i]

# max(0, max_at(i-1)) : lst[i-1]까지의 부분 구간 합

# lst[i] : 새로 추가된 값

 

이 식을 코드로 구현하면 아래와 같다. 이 코드는 딱 하나의 반복문을 갖고 있기 때문에 시간 복잡도는 O(N)이 된다.

 

def fastest_max_sum(lst):
    N = len(lst)
    ret = float('-inf')
    psum = 0
    for i in range(N):
        psum = max(psum, 0) + lst[i]
        ret = max(psum, ret)
    
    return ret
 
if __name__ == "__main__":
    lst = [-7, 4, -3, 6, 3, -8, 3, 4]
    print(fastest_max_sum(lst))
 
# 10

---

 

위의 알고리즘들의 수행 시간

이제 위의 알고리즘들의 수행 시간을 예측해보도록 하겠다. 만약 시간제한이 1초이고 N의 상한이 1000, 10000, 100000일 때 이 중 어떤 알고리즘을 사용할 수 있을까?

 

N = 1000 : N^3은 10억으로 우리의 예상 기준을 넘어서기 때문에 알고리즘을 사용할 때 주의하는 것이 좋다.

N = 10000 : N^3은 1조이므로 돌아갈 가능성이 거의 없다. N^2는 1억 정도이므로 주의해야 할 범위에 들어간다.

N = 100000 : 이때는 N^2도 100억이 된다. 따라서 O(N^2) 알고리즘도 시간 안에 돌아갈 가능성이 높지 않다. 반면 N log N은 대략 2천만 정도이므로 비교적 수월하게 돌아갈 것으로 예상된다.

 

시간 복잡도는 알고리즘의 특성이지 문제의 특성이 아니다. 한 문제를 푸는 두 가지 이상의 알고리즘이 있을 수 있고, 이들의 시간 복잡도는 각각 다를 수 있기 때문이다.