복잡도

탐욕 알고리즘의 비용은 대부분 정렬이나 우선순위 큐 연산에서 나옵니다. 선택 자체는 후보마다 상수 시간인 경우가 많기 때문입니다. 그래서 대표 탐욕 알고리즘의 시간 복잡도는 대개 O(n log n)이고, 입력이 이미 정렬되어 있으면 O(n)까지 내려갑니다.

대표 문제별 복잡도

최선, 평균, 최악의 차이는 거의 없습니다. 정렬은 입력 모양과 상관없이 O(n log n)이 들고(Python의 Timsort는 이미 정렬된 입력에서 O(n)), 이후 훑기는 언제나 한 번입니다. 회의실 배정에서 힙 크기는 동시에 열린 회의 수 k를 넘지 않으므로 더 정확히는 O(n log k)입니다.

큐 두 개로 만드는 O(n) 허프만

빈도가 이미 오름차순으로 정렬되어 있다면 힙 없이 큐 두 개로 허프만 비용을 구할 수 있습니다. 합쳐서 생기는 무게는 항상 커지는 순서로 나오기 때문에, 두 번째 큐도 저절로 정렬 상태를 유지합니다.

from collections import deque


def huffman_cost_sorted(weights):
    """오름차순 빈도를 받아 전체 비트 수를 O(n)에 구한다."""
    leaves, merged = deque(weights), deque()

    def pop_min():
        if not merged or (leaves and leaves[0] <= merged[0]):
            return leaves.popleft()
        return merged.popleft()

    total = 0
    while len(leaves) + len(merged) > 1:
        a = pop_min()
        b = pop_min()
        total += a + b
        merged.append(a + b)
    return total


print(huffman_cost_sorted([5, 9, 12, 13, 16, 45]))  # 224

힙 없이 회의실 세기

회의실 수만 필요하다면 시작 시간과 끝 시간을 따로 정렬해 두 포인터로 훑어도 됩니다. 시간은 똑같이 O(n log n)이지만 상수가 작고 코드가 짧습니다. 다만 어느 회의가 어느 방에 들어가는지는 알 수 없으므로, 배정 결과가 필요하면 힙 방식을 씁니다.

def min_rooms_sweep(meetings):
    starts = sorted(s for s, _ in meetings)
    ends = sorted(e for _, e in meetings)
    rooms = j = 0
    for s in starts:
        if ends[j] <= s:
            j += 1      # 끝난 회의의 방을 넘겨받는다
        else:
            rooms += 1  # 방을 하나 더 연다
    return rooms


print(min_rooms_sweep([(9, 10), (9, 12), (10, 11), (11, 13), (12, 13)]))  # 2

다른 방법과 비교

표에서 보듯 탐욕이 맞는 문제에서는 다른 방법보다 훨씬 빠르고 메모리도 적게 씁니다. 반대로 문제를 조금만 바꿔도(가중치 추가, 쪼갤 수 없는 물건) 탐욕은 정답을 보장하지 못합니다. 문제 조건이 바뀌면 복잡도보다 먼저 정당성을 다시 따져야 합니다.

직접 재 보기

이론상 복잡도는 실제 실행 시간으로 확인해 볼 수 있습니다. n이 10배가 될 때 시간이 10배보다 조금 더 늘어나면 O(n log n)에 맞는 모습입니다.

import random
import time


def max_count(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            count, last_end = count + 1, end
    return count


for n in (10_000, 100_000, 1_000_000):
    data = [(s, s + random.randint(1, 100)) for s in (random.randint(0, 10**6) for _ in range(n))]
    t = time.perf_counter()
    max_count(data)
    print(n, f"{time.perf_counter() - t:.3f}s")

정리

• 탐욕 알고리즘의 시간은 주로 정렬이나 힙이 결정하며 대개 O(n log n)입니다.
• 입력이 이미 정렬되어 있으면 활동 선택과 허프만 모두 O(n)으로 줄일 수 있습니다.
• 회의실 수만 필요하면 두 포인터 방식, 배정 결과가 필요하면 힙 방식을 씁니다.
• 탐욕은 맞을 때 가장 빠르지만, 가중치나 분할 불가 조건이 붙으면 동적 계획법으로 바꿔야 합니다.