Жадные алгоритмы и разделяй-властвуй

Жадный выбор и условия его корректности, задача о размене и о расписании, алгоритм Хаффмана, схема разделяй-властвуй, основная теорема о рекуррентах.

Две классические стратегии проектирования алгоритмов. Жадная берёт лучшее на каждом шаге и никогда не пересматривает решение. Разделяй-властвуй разбивает задачу на части, решает их независимо и объединяет результаты.

Жадный подход

Схема:
  1. Отсортировать элементы по некоторому критерию
  2. Идти по порядку и брать элемент, если он не нарушает ограничений
  3. Не возвращаться к принятым решениям

Сложность обычно определяется сортировкой: O(n log n)

Жадность работает не всегда — и это главное, что нужно понимать. Она даёт оптимум только при выполнении двух условий: свойство жадного выбора (локально лучший шаг входит в оптимальное решение) и оптимальность подзадач.

Когда жадность работает

# Задача о выборе заявок: максимум непересекающихся интервалов
def max_activities(intervals):
    """Ключ к решению — сортировка по времени ОКОНЧАНИЯ."""
    intervals = sorted(intervals, key=lambda x: x[1])
    chosen, last_end = [], float('-inf')
    for start, end in intervals:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

tasks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_activities(tasks))   # [(1,4), (5,7), (8,11)] — три заявки

Когда жадность ошибается

def greedy_change(amount, coins):
    """Жадный размен: берём самую крупную монету."""
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        while amount >= c:
            result.append(c)
            amount -= c
    return result if amount == 0 else None

# Для российских монет работает
print(greedy_change(37, [1, 2, 5, 10]))      # [10,10,10,5,2] — 5 монет, оптимум

# А для такого набора — нет
print(greedy_change(30, [1, 15, 25]))        # [25,1,1,1,1,1] — 6 монет
# Оптимум: [15, 15] — две монеты

# Правильно — динамическое программирование
def dp_change(amount, coins):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] < INF else None

print(dp_change(30, [1, 15, 25]))            # 2

Отсюда практическое правило: прежде чем применять жадный алгоритм, найдите контрпример или докажите корректность. В курсовой такое сравнение с динамическим программированием на конкретных данных ценится выше, чем просто работающий код.

Алгоритм Хаффмана

import heapq
from collections import Counter

def huffman_codes(text):
    freq = Counter(text)
    if len(freq) == 1:
        return {next(iter(freq)): '0'}

    heap = [[w, i, {ch: ''}] for i, (ch, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(heap)

    while len(heap) > 1:
        w1, _, c1 = heapq.heappop(heap)      # два самых редких
        w2, _, c2 = heapq.heappop(heap)
        merged = {}
        for ch, code in c1.items(): merged[ch] = '0' + code
        for ch, code in c2.items(): merged[ch] = '1' + code
        heapq.heappush(heap, [w1 + w2, counter, merged])
        counter += 1

    return heap[0][2]

text = 'алгоритм анализ алгоритм данные'
codes = huffman_codes(text)

bits_before = len(text) * 8
bits_after = sum(len(codes[ch]) for ch in text)
print(f'было {bits_before} бит, стало {bits_after} бит, '
      f'сжатие {100 - bits_after/bits_before*100:.0f}%')

Жадный шаг здесь — слияние двух наименее частых символов. Он доказуемо оптимален, поэтому код Хаффмана даёт минимально возможную среднюю длину среди префиксных кодов. Это ядро форматов ZIP, JPEG и MP3.

Разделяй и властвуй

Схема из трёх шагов:
  1. Разделить задачу на a подзадач размера n/b
  2. Решить каждую рекурсивно
  3. Объединить решения за время f(n)

Рекуррентное соотношение:
  T(n) = a·T(n/b) + f(n)

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])           # разделяем
    right = merge_sort(a[mid:])
    return merge(left, right)            # объединяем за O(n)

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:]); res.extend(b[j:])
    return res

# T(n) = 2T(n/2) + O(n)  →  O(n log n)

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

# T(n) = T(n/2) + O(1)  →  O(log n)

Основная теорема о рекуррентах

Для T(n) = a·T(n/b) + O(n^d):

  если d > log_b(a):   T(n) = O(n^d)              — объединение доминирует
  если d = log_b(a):   T(n) = O(n^d · log n)      — вклады равны
  если d < log_b(a):   T(n) = O(n^(log_b a))      — рекурсия доминирует

Примеры:
  сортировка слиянием: a=2, b=2, d=1 → log₂2 = 1 = d → O(n log n)
  бинарный поиск:      a=1, b=2, d=0 → log₂1 = 0 = d → O(log n)
  умножение Карацубы:  a=3, b=2, d=1 → log₂3 ≈ 1,585 > 1 → O(n^1,585)

Сравнение стратегий

Известные жадные алгоритмы

• Дейкстры — кратчайшие пути от одной вершины при неотрицательных весах.
• Прима и Краскала — минимальное остовное дерево.
• Хаффмана — оптимальное префиксное кодирование.
• Планирование заявок по времени окончания.
• Непрерывный рюкзак: берём по убыванию отношения ценности к весу. Для дискретного рюкзака жадность уже не работает — нужно ДП.