알고리즘의 시간 복잡도 분석 (2)

• 저번 글에 이어서 시간 복잡도와 관련된 빅 오 표기법(big-O notation), 주먹구구 법칙, NP 문제 등을 다뤄보겠습니다.

 

시간 복잡도

• 지난 글을 돌이켜보면 알고리즘을 평가할 때 중요한 지표 중 하나는 바로 '시간 복잡도'였습니다. 이 시간 복잡도는 알고리즘이 얼마나 효율적으로 실행되는지를 나타내는 척도로, 알고리즘이 수행하는 기본 연산의 총 횟수를 입력 크기에 따라 나타낸 것입니다.
• 기본 연산은 더 이상 쪼갤 수 없는 최소 단위의 연산으로, 예를 들어 정수의 사칙연산, 변수 간의 대입, 논리 연산 등이 이에 해당합니다. 이와 달리 배열 정렬, 문자열 비교, 소인수 분해 같은 연산들은 여러 기본 연산을 포함하므로 기본 연산으로 분류되지 않습니다.
• 시간 복잡도의 핵심은 알고리즘 내부의 '가장 깊이 중첩된 반복문'입니다. 반복문 내부에서 수행되는 기본 연산들이 알고리즘의 전체 수행 시간을 결정합니다. 따라서 가장 깊은 반복문의 수행 횟수를 분석하면 알고리즘의 시간 복잡도를 대략적으로 파악할 수 있습니다.

 

• 시간 복잡도가 높다는 것은 입력 크기가 커질수록 알고리즘의 수행 시간이 빠르게 증가한다는 의미입니다.
• 그렇지만 이것이 무조건 느린 알고리즘임을 의미하지는 않습니다. 예를 들어, 입력 크기가 작을 때에는 시간 복잡도가 높은 알고리즘이 더 빠르게 수행될 수 있습니다. 반면, 입력 크기가 커지면 시간 복잡도가 낮은 알고리즘이 더 효율적입니다.
• 시간 복잡도를 더 자세히 이해하려면 입력의 종류도 고려해야 합니다.
• 예를 들어 배열의 원소를 선형 탐색하는 경우, 원소의 위치에 따라 수행 시간이 달라질 수 있습니다. 이를 반영하여 알고리즘의 최선, 최악, 평균적인 경우의 수행 시간을 분석합니다.

# 선형 탐색

# array[i] = element인 첫 i를 반환합니다. 없으면 -1을 반환합니다.
def first_index(array: list, element: int) -> int:
    for i in range(len(array)):
        if array[i] == element:
            return i
    return -1

 

• 시간 복잡도를 간결하게 표현하기 위해 사용되는 방법 중 하나가 '빅 오 표기법(big-O notation)'입니다. 이 방법은 함수에서 가장 빠르게 증가하는 항만을 남기고 나머지를 생략하여 알고리즘의 수행 시간의 상한을 표현합니다.
• 예를 들어, 수행 시간이 $N^2 + 100N + 1$인 알고리즘의 시간 복잡도는 $O(N^2)$으로 표현됩니다.

문제	반복문의 수행 횟수	O 표기
이동 평균	$N$	$O(N)$
이진 탐색	$logN$	$O(logN)$
집합 덮개	$N\cdot M\cdot2^M$	$O(N\cdot M\cdot2^M)$

• 선택 정렬과 삽입 정렬은 두 가지 다른 $O(N^2)$ 시간 복잡도를 가진 정렬 알고리즘입니다.
• 선택 정렬은 모든 경우에 $O(N^2)$의 시간 복잡도를 보이지만, 삽입 정렬은 최선의 경우 $O(1)$의 효율성을 보일 수 있습니다.

# 선택 정렬과 삽입 정렬

def selection_sort(A: list) -> None:
    for i in range(len(A)):
        min_index = i
        for j in range(i+1, len(A)):
            if A[min_index] > A[j]:
                min_index = j
        A[i], A[min_index] = A[min_index], A[i]

def insertion_sort(A: list) -> None:
    for i in range(len(A)):
        # A[0..i-1]에 A[j]를 끼워넣습니다.
        j = i
        while j > 0 and A[j-1] > A[j]:
            A[j-1], A[j] = A[j], A[j-1]
            j -= 1

• 분할 상환 분석은 알고리즘의 평균 수행 시간을 보다 정확하게 파악하는 데 사용됩니다.
• 이 분석은 여러 작업의 평균 수행 시간을 계산할 때 유용하며, 각 작업의 수행 시간이 다를지라도 전체 작업에 걸리는 총 시간이 일정한 경우에 적용됩니다.

 

수행 시간 어림짐작하기

• 프로그래밍 대회에서 시간 제한을 고려할 때, 주먹구구 법칙은 매우 유용합니다. 이는 시간 복잡도와 입력 크기를 바탕으로 알고리즘의 수행 시간을 대략적으로 추정하는 방법입니다.
• 시간 복잡도는 알고리즘 수행 시간에 가장 큰 영향을 미치는 요소이기 때문에, 이를 통해 어떤 알고리즘이 주어진 시간 안에 문제를 해결할 수 있을지 예측할 수 있습니다.
• 대략적인 규칙은 1초당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 초과의 가능성이 있다는 것입니다.
• 예를 들어, 입력 크기 N이 10,000이고 알고리즘의 시간 복잡도가 $O(N^{3})$일 경우, 반복문 수행 횟수는 1000억이 되어 시간 제한을 초과할 가능성이 높습니다.
• 반면에 $O(N^2)$나 $O$$($$N\cdot logN$$)$은 이 범위 내에 들어와 시간 내에 실행될 가능성이 있습니다.
• 하지만 주먹구구 규칙이 절대적이진 않습니다! 실제 프로그램의 수행 시간은 CPU 속도, 메모리 접근 패턴, 컴파일러의 최적화 등 여러 요인에 의해 영향을 받기 때문입니다.
• 따라서 이 법칙은 대략적인 가이드라인으로만 사용해야 하며, 예측이 틀릴 수도 있다는 점을 항상 염두에 두어야 합니다.

 

• 실제 프로그래밍 대회에서는 각각의 알고리즘에 대한 시간 복잡도를 분석하여 적절한 알고리즘을 선택하는 것이 중요합니다.
• 예를 들어, 연속된 부분 구간의 최대 합을 찾는 문제를 풀 때 $O(N^{3})$, $O(N^2)$, $O$$($$N\cdot logN$$)$, 그리고 $O(N)$의 시간 복잡도를 갖는 다양한 알고리즘을 고려할 수 있습니다.

# 최대 연속 부분 구간 합 문제를 푸는 무식한 알고리즘들

# A[]의 연속된 부분 구간의 최대 합을 구합니다. 
# 시간 복잡도: O(N^3)
def inefficient_max_sum(A: list) -> int:
    N, result = len(A), -float('inf')
    for i in range(N):
        for j in range(i, N):
            # 구간 A[i..j]의 합을 구합니다.
            sum = 0
            for k in range(i, j+1):
                sum += A[k]
            result = max(result, sum)
    return result

# A[]의 연속된 부분 구간의 최대 합을 구합니다. 
# 시간 복잡도: O(N^2)
def better_max_sum(A: list) -> int:
    N, result = len(A), -float('inf')
    for i in range(N):
        sum = 0
        for j in range(i, N):
            sum += A[j]
            result = max(result, sum)
    return result

# 최대 연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘

# A[lo..hi]의 연속된 부분 구간의 최대 합을 구합니다.
# 시간 복잡도: O(NlgN)
import sys
def fast_max_sum(A: list, lo: int, hi: int):
    # 기저 사례: 구간의 길이가 1일 경우
    if lo == hi:
        return A[lo]
    # 배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눕니다.
    mid = (lo + hi) // 2
    # 두 부분에 모두 걸쳐 있는 최대 합 구간을 찾습니다. 이 구간은
    # A[i..mid]와 A[mid+1..j] 형태를 가지는 구간의 합으로 이루어집니다.
    # A[i..mid] 형태를 갖는 최대 구간을 찾습니다.
    left, right, sum = -sys.maxsize, -sys.maxsize, 0
    for i in range(mid, lo - 1, -1):
        sum += A[i]
        left = max(left, sum)
    # A[mid+1..j] 형태를 갖는 최대 구간을 찾습니다.
    sum = 0
    for j in range(mid + 1, hi + 1):
        sum += A[j]
        right = max(right, sum)
    # 최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾습니다.
    single = max(fast_max_sum(A, lo, mid),
                 fast_max_sum(A, mid + 1, hi))
    # 두 경우 중 최대치를 반환합니다.
    return max(left + right, single)

# 최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘

# A[]의 연속된 부분 구간의 최대 합을 구합니다.
# 시간 복잡도: O(N)
def fastest_max_sum(A: list) -> int:
    N, result, p_sum = len(A), -float('inf'), 0
    for i in range(N):
        p_sum = max(p_sum, 0) + A[i]
        result = max(p_sum, result)
    return result

• $O(N^{3})$ 알고리즘: 이 알고리즘은 2560 크기의 입력까지 1초 안에 처리할 수 있으며, 이 때의 반복문 수행 횟수는 대략 160억 회입니다.
• $O(N^2)$ 알고리즘: 40960 크기의 입력까지 1초 안에 처리 가능하며, 여기서의 반복문 수행 횟수는 대략 16억 회입니다.
• $O$$($$N\cdot logN$$)$ 알고리즘: 약 2천만 크기의 입력까지 1초 안에 처리할 수 있으며, 반복문 수행 횟수는 대략 5억 회입니다.
• $O(N)$ 알고리즘: 약 1억 6천만 크기의 입력까지 1초 안에 처리할 수 있습니다.

 

계산 복잡도 클래스: P, NP, NP-완비

• 계산 복잡도 이론은 문제를 푸는 알고리즘의 시간 복잡도를 기준으로 문제의 난이도를 정의합니다.
• 각 문제는 다양한 알고리즘으로 해결될 수 있으며, 이 알고리즘들은 각각 다른 시간 복잡도를 가질 수 있습니다.
• 예를 들어, 정렬 문제와 부분 집합의 합 문제는 각각 다른 방식으로 접근할 수 있는데, 이를 통해 문제의 '어려움'은 문제를 해결하는 가장 효율적인 알고리즘의 존재 유무에 의해 결정된다는 것을 알 수 있습니다.

 

• 계산 복잡도 이론에서 중요한 두 클래스는 P 문제와 NP 문제입니다.
• P 문제는 다항 시간 내에 해결될 수 있는 문제들을 의미하고, NP 문제는 답이 주어졌을 때 그것이 정답인지를 다항 시간 내에 확인할 수 있는 문제들을 말합니다.
• 모든 P 문제는 NP 문제에 속하지만, 모든 NP 문제가 P 문제인지는 아직 해결되지 않은 문제입니다.
• NP 문제 중에서도 특히 중요한 것이 NP-난해와 NP-완비 문제입니다.
• NP-난해 문제는 모든 NP 문제가 이 문제로 환산될 수 있으며, NP-완비 문제는 NP-난해이면서 NP에 속하는 문제입니다. 가장 유명한 NP-완비 문제 중 하나는 SAT(Satisfiability) 문제입니다.

 

• 계산 복잡도 이론의 핵심적인 질문 중 하나는 P와 NP가 동일한지 여부, 즉 P=NP 문제입니다. 이 문제는 NP 문제 중 하나가 다항 시간 내에 해결될 수 있다면 모든 NP 문제가 다항 시간 내에 해결될 수 있음을 의미합니다.
• 이는 아직 해결되지 않았으며, 계산 복잡도 이론의 핵심적인 미해결 문제 중 하나입니다.
• 계산 복잡도 이론은 이론적인 배경을 가지고 있지만, 실제 문제 해결에 있어서도 중요한 지침을 제공합니다. 어떤 문제가 NP-난해나 NP-완비로 분류된다면, 이 문제를 효율적으로 푸는 것은 매우 어려운 일임을 알 수 있습니다.
• 이럴 때는 다른 접근 방식을 고려하거나 근사해를 찾는 것이 현실적인 해결책이 될 수 있습니다.