def binary_search(sorted_arr, target):
    left, right = 0, len(sorted_arr) - 1
    steps = 0
    while left <= right:
        steps += 1
        mid = (left + right) // 2
        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Поиск среди 16 отсортированных элементов займет не более 4 шагов.

Помимо временной, важна и пространственная сложность, которая оценивает объем дополнительной памяти, требуемой алгоритмом. Например, алгоритм нахождения максимума в массиве использует фиксированный объем памяти O(1), тогда как создание полной копии списка потребует памяти O(n).

Практическое значение асимптотического анализа становится очевидным при сравнении алгоритмов. Рассмотрим задачу поиска дубликатов. Наивный подход с двойным циклом имеет сложность O(n²):

def find_duplicates_slow(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

Более разумный подход с использованием хэш-множества имеет сложность O(n):

def find_duplicates_fast(arr):
    seen = set()
    duplicates = set()
    for item in arr:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return list(duplicates)

На списке из тысячи элементов второй алгоритм окажется в сотни раз быстрее первого.

Для наглядности можно представить себе сводную таблицу сложностей. O(1) обозначает мгновенное выполнение, например доступ к элементу массива по индексу. O(log n) характерна для алгоритмов типа бинарного поиска. O(n) — для линейного прохода по данным. O(n log n) — это типичная сложность эффективных алгоритмов сортировки. O(n²) часто возникает при обработке матриц или использовании вложенных циклов. O(2ⁿ) — экстремально медленная сложность, присущая некоторым задачам полного перебора.

Понимание этих принципов позволяет делать осознанный выбор алгоритма, что является фундаментальным навыком в разработке эффективных программ.

#algorithm

Тем не менее, рекурсия остаётся незаменимым инструментом для задач, имеющих естественную рекурсивную структуру данных или логики. Она идеально подходит для обхода древовидных структур (каталогов файловой системы), реализации алгоритмов "разделяй и властвуй" (быстрая сортировка, бинарный поиск) и решения таких задач, как Ханойские башни. Выбор между рекурсией и итерацией часто является компромиссом между читаемостью, простотой выражения идеи алгоритма и требованиями к производительности и ресурсам.

#algorithm

Интересной задачей является реализация очереди с помощью двух стеков. Классическое решение использует один стек для добавления элементов (enqueue), а другой — для удаления (dequeue). Когда требуется удалить элемент, но второй стек пуст, все элементы перекладываются из первого стека во второй, в результате чего порядок инвертируется и первый добавленный элемент оказывается на вершине второго стека, готовый к извлечению.

Пример 8

Это работает, потому что при перекладывании элементов из одного стека в другой их порядок обращается, что и позволяет имитировать поведение очереди.

Помимо уже упомянутых случаев, стек используется во многих других областях. История браузера — это классический пример, где посещенные страницы складываются в стек для кнопки «Назад».

Пример 9

Функция отмены действий в редакторах также полагается на стек для хранения состояний.

Пример 10

Стек вызовов, управляющий выполнением функций в программе, — еще один яркий пример. Когда функция вызывает другую, ее контекст помещается в стек, а после завершения вложенной функции — восстанавливается.

Пример 11

Проверка корректности HTML-тегов — задача, где стек отслеживает вложенность открывающих и закрывающих элементов.

Пример 12

Для реализации очереди в Python оптимально использовать класс deque из модуля collections. Это двусторонняя очередь, которая обеспечивает константную сложность O(1) для операций добавления и удаления с обоих концов, в отличие от списка, где удаление из начала (pop(0)) имеет линейную сложность O(n). Полноценная реализация очереди на deque включает все основные операции.

Пример 13

Практическим применением может служить система обработки заказов, где каждый новый заказ ставится в очередь и обрабатывается по мере возможности.

Пример 14

С точки зрения сложности операций, стек на основе списка Python обеспечивает O(1) для push, pop и peek, так же как и проверка на пустоту. Очередь на основе deque также гарантирует O(1) для enqueue, dequeue, front и isEmpty. Важно подчеркнуть, что использование обычного списка для очереди неэффективно из-за линейной сложности операции pop(0), что делает deque предпочтительным выбором.

В заключение, стек и очередь — это фундаментальные структуры данных, каждая со своим строгим принципом доступа: LIFO для стека, подобно стопке тарелок, и FIFO для очереди, как очередь людей. Их понимание критически важно для изучения алгоритмов и системного программирования, поскольку они лежат в основе множества механизмов — от управления памятью и планирования процессов до синтаксического анализа и работы с историей. Ключевые моменты для запоминания: стек оперирует с одним концом, очередь — с двумя; в Python для стека используется list, для очереди — deque; обе структуры обеспечивают высокую эффективность основных операций.

#algorithm

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Пример 1: Обычная сортировка
data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data1.copy()))
# Результат: [11, 12, 22, 25, 34, 64, 90]

# Пример 2: Уже отсортированный список
data2 = [1, 2, 3, 4, 5]
print(bubble_sort(data2.copy()))
# Результат: [1, 2, 3, 4, 5]

# Пример 3: Обратный порядок
data3 = [5, 4, 3, 2, 1]
print(bubble_sort(data3.copy()))
# Результат: [1, 2, 3, 4, 5]

Чтобы лучше проследить за ходом алгоритма, можно использовать визуализированную версию:

def bubble_sort_visualized(arr):
    n = len(arr)
    print(f"Начальный список: {arr}")
    print()
    
    for i in range(n):
        print(f"=== Проход {i + 1} ===")
        swapped = False
        
        for j in range(0, n - i - 1):
            print(f"Сравниваем {arr[j]} и {arr[j + 1]}", end=" ")
            
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f"→ Меняем! Теперь: {arr}")
            else:
                print(f"→ Оставляем")
        
        if not swapped:
            print("Обменов не было, список отсортирован!")
            break
        print()
    
    print(f"\nИтоговый список: {arr}")
    return arr

data = [5, 2, 8, 1, 9]
bubble_sort_visualized(data)

Одним из недостатков пузырьковой сортировки является её низкая эффективность на больших наборах данных. Сложность алгоритма в худшем и среднем случае оценивается как O(n²), где n — количество элементов. Это означает, что с ростом размера списка количество необходимых операций сравнения и обмена растёт квадратично. Например, для тысячи элементов может потребоваться около миллиона сравнений, в то время как более совершенные алгоритмы, такие как быстрая сортировка, справляются с этой задачей за порядка двадцати тысяч операций. Именно поэтому пузырьковая сортировка, при всей своей простоте и наглядности, не применяется в реальных проектах с большими объёмами данных.

Алгоритм можно модифицировать для сортировки по убыванию. Для этого достаточно изменить условие сравнения с > на <, чтобы более мелкие элементы перемещались вправо:

def bubble_sort_descending(arr):
    """Пузырьковая сортировка в порядке УБЫВАНИЯ."""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_descending(data1.copy()))
# Результат: [90, 64, 34, 25, 22, 12, 11]

Также можно создать универсальную функцию, принимающую параметр reverse для выбора направления сортировки.

В заключение, пузырьковая сортировка служит отличным учебным инструментом для понимания базовых принципов алгоритмов сортировки. Она проста для восприятия и реализации, корректно работает на любых данных, но из-за квадратичной сложности неприменима для серьёзных задач. Её изучение даёт необходимую основу для перехода к более эффективным алгоритмам.

#algorithm

def quick_sort(arr):
    """Быстрая сортировка списка."""
    # Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if len(arr) <= 1:
        return arr
    else:
        # Выбираем опорный элемент (средний по индексу)
        pivot = arr[len(arr) // 2]
        
        # Создаём три подмассива:
        # left - все элементы меньше опорного
        left = [x for x in arr if x < pivot]
        
        # middle - все элементы равные опорному
        middle = [x for x in arr if x == pivot]
        
        # right - все элементы больше опорного
        right = [x for x in arr if x > pivot]
        
        # Рекурсивно сортируем левую и правую части,
        # объединяем результаты
        return quick_sort(left) + middle + quick_sort(right)

Наличие группы middle в реализации принципиально важно для корректной обработки массивов с повторяющимися элементами. Без неё алгоритм может попасть в бесконечную рекурсию, пытаясь сортировать одинаковые значения.

Производительность быстрой сортировки в первую очередь зависит от выбора опорного элемента. Хороший выбор, когда пивот делит массив примерно пополам, приводит к временной сложности O(n log n) в лучшем и среднем случаях. Это происходит потому, что глубина рекурсии составляет log n уровней, и на каждом уровне выполняется порядка n операций. Однако если опорный элемент постоянно оказывается минимальным или максимальным, дерево рекурсии становится несбалансированным, что приводит к худшему случаю со сложностью O(n²). Для улучшения выбора пивота применяют такие методы, как случайный выбор или выбор медианы из трех элементов — первого, среднего и последнего. Например:

import random
pivot = arr[random.randint(0, len(arr)-1)]

Пространственная сложность представленной реализации составляет O(n), так как на каждом уровне рекурсии создаются новые списки. Однако существует оптимизированная версия алгоритма, выполняющая сортировку на месте, которая требует O(log n) дополнительной памяти для стека рекурсии.

Сравнение быстрой сортировки с сортировкой слиянием выявляет их ключевые различия. Оба алгоритма имеют среднюю сложность O(n log n), но сортировка слиянием гарантирует эту сложность даже в худшем случае, тогда как быстрая сортировка может деградировать до O(n²). С другой стороны, быстрая сортировка часто оказывается быстрее на практике из-за меньших константных множителей и может быть реализована с меньшим потреблением памяти. Сортировка слиянием является стабильной — она сохраняет относительный порядок равных элементов, что не всегда верно для классической in-place реализации быстрой сортировки.

Встроенная функция sort() в Python использует более сложный гибридный алгоритм — Timsort. Он сочетает в себе идеи сортировки слиянием и сортировки вставками. Timsort эффективно использует уже существующие упорядоченные подпоследовательности в данных, что делает его особенно быстрым для частично отсортированных массивов, где он может достигать сложности O(n). Этот алгоритм является стабильным и гарантирует производительность O(n log n) в худшем случае, что делает его отличным выбором для стандартной библиотеки Python. Пример его использования:

data = [64, 34, 25, 12, 22, 11, 90]
data.sort()
sorted_data = sorted(data, reverse=True)

Таким образом, быстрая сортировка остается важным и фундаментальным алгоритмом, наглядно демонстрирующим принцип «разделяй и властвуй». Она эффективна на практике, хотя и требует внимательного подхода к выбору опорного элемента. Для большинства повседневных задач предпочтительнее использовать оптимизированные встроенные средства языка, такие как Timsort в Python, но глубокое понимание работы быстрой сортировки необходимо для анализа алгоритмов и решения специализированных задач.

#algorithm

Подводя итог, можно выделить ключевые характеристики бинарного поиска. Во-первых, он применим исключительно к отсортированным массивам. Во-вторых, его временная сложность O(log n) делает его чрезвычайно быстрым для больших наборов данных. В-третьих, принцип работы основан на постоянном уменьшении области поиска вдвое. Наконец, алгоритм возвращает индекс найденного элемента или специальное значение (например, -1), если элемент отсутствует. По сравнению с линейным поиском бинарный поиск демонстрирует подавляющее преимущество в скорости на крупных массивах, что делает его одним из фундаментальных алгоритмов в информатике.

#algorithm

def delete_by_value(self, data):
    # Случай 1: Список пустой
    if not self.head:
        return
    
    # Случай 2: Удаляем голову
    if self.head.data == data:
        self.head = self.head.next  # Просто сдвигаем голову
        return
    
    # Случай 3: Удаляем элемент из середины/конца
    current_node = self.head
    
    # Ищем узел ПЕРЕД тем, который нужно удалить
    while current_node.next:
        if current_node.next.data == data:
            # "Перепрыгиваем" через удаляемый узел
            current_node.next = current_node.next.next
            return
        current_node = current_node.next

Наглядно этот процесс выглядит так:

Исходный список:
head → [10|•]→[20|•]→[30|•]→[40|×]

Удаляем 20:

Шаг 1: Находим узел ПЕРЕД удаляемым
head → [10|•]→[20|•]→[30|•]→[40|×]
       ↑       ↑
    current  current.next (удаляем это)

Шаг 2: "Перепрыгиваем" через 20
current.next = current.next.next

head → [10|•]─────→[30|•]→[40|×]
             \    /
              [20|•] (потерян, будет удален сборщиком мусора)

Пример использования:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.append(40)

print(ll.display())  # [10, 20, 30, 40]

ll.delete_by_value(20)
print(ll.display())  # [10, 30, 40]

ll.delete_by_value(10)  # Удаляем голову
print(ll.display())  # [30, 40]

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

class DoubleNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # Ссылка вперед
        self.prev = None  # Ссылка назад

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

Двусвязный список:
None ← head                    tail → None
       [×|10|•]↔️[•|20|•]↔️[•|30|×]
        ↑    ↑    ↑    ↑    ↑    ↑
       prev next prev next prev next

Реализация двусвязного списка включает поддержку ссылки не только на голову, но и на хвост.

Пример 2

Пример показывает его новые возможности:

dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)

print(dll.display_forward())   # [10, 20, 30]
print(dll.display_backward())  # [30, 20, 10]

Преимущества двусвязного списка включают возможность двустороннего обхода, более простое удаление узла, так как ссылка на предыдущий элемент уже известна, и добавление в конец за O(1) благодаря наличию ссылки на хвост. Однако за эти удобства приходится платить дополнительной памятью на хранение второй ссылки в каждом узле и усложнением логики управления связями.

Таким образом, связный список — это гибкая и динамическая структура данных, идеально подходящая для сценариев, где часто требуется изменение порядка элементов, особенно в начале списка, или когда окончательный размер коллекции заранее неизвестен. Массивы же остаются лучшим выбором, когда критически важен быстрый произвольный доступ к элементам по их индексу.

#algorithm

Метод цепочек для разрешения коллизий, как уже упоминалось, заключается в хранении в каждой ячейке массива связного списка всех пар «ключ-значение», которым соответствует данный индекс. При вставке нового элемента с ключом, чей хеш совпал с хешом уже существующего, новая пара добавляется в конец списка этой ячейки. Поиск требует вычисления хеша и последующего последовательного просмотра списка для нахождения нужного ключа. Основное преимущество метода цепочек — его простота и то, что таблица никогда не переполняется, так как список может расти динамически. Недостатком является необходимость в дополнительной памяти для хранения ссылок и потенциальное снижение производительности при длинных цепочках.

Пример 5

Использование хеш-таблиц наиболее оправдано в задачах, требующих частых операций поиска, проверки наличия элемента или подсчёта уникальных значений. Это включает подсчёт частоты элементов в коллекции, поиск дубликатов, реализацию кэшей, решение задачи о двух суммах, группировку данных по определённому признаку, представление графов в виде списков смежности, поиск анаграмм и реализацию множеств. Например, задача поиска двух чисел в массиве, дающих в сумме заданное значение, эффективно решается за один проход с использованием хеш-таблицы для хранения просмотренных элементов.

# Решение задачи "Две суммы" с использованием хеш-таблицы
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return None

numbers = [2, 7, 11, 15]
target = 9
print(two_sum(numbers, target))  # [0, 1] (2 + 7 = 9)

Однако существуют сценарии, где хеш-таблицы могут быть не самым лучшим выбором. Если требуется упорядоченный обход элементов по ключу, данные необходимо часто сортировать или выполнять поиск по диапазону ключей, более подходящими структурами могут оказаться сбалансированные деревья поиска. Также хеш-таблицы требуют дополнительной памяти и могут иметь неоптимальную производительность при очень высокой нагрузке и плохой хеш-функции.

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

#algorithm

Полная последовательность работы программы, создающей дерево и выводящей отсортированный список, демонстрирует практическую пользу структуры.

root = TreeNode(10)
insert(root, 5)
insert(root, 15)
insert(root, 2)
insert(root, 7)
print(inorder_traversal(root))

Однако у простого BST есть существенный недостаток. Если вставлять в него элементы в уже отсортированном порядке, например, 1, 2, 3, 4, 5, дерево выродится в простую цепочку, где каждый новый элемент будет становиться правым потомком предыдущего. В таком случае дерево теряет свое главное преимущество — логарифмическую сложность операций, — и поиск элемента начинает требовать линейного времени, как в обычном списке. Эта проблема иллюстрирует необходимость в более совершенных структурах.

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

Для решения проблемы вырождения существуют самобалансирующиеся деревья, такие как AVL-дерево или красно-черное дерево. Они автоматически перестраиваются при вставке и удалении элементов, поддерживая свою высоту близкой к логарифмической относительно числа узлов. Это гарантирует, что операции поиска, вставки и удаления всегда будут выполняться за время, пропорциональное логарифму числа элементов, даже в худшем случае. Например, в сбалансированном дереве из миллиона элементов поиск потребует около двадцати сравнений, в то время как в вырожденном дереве-цепочке он может дойти до миллиона операций.

Таким образом, путь развития от общей концепции дерева до самобалансирующихся структур демонстрирует эволюцию идеи: от иерархического хранения данных через введение строгих правил упорядочивания для ускорения поиска к реализации механизмов самоконтроля для гарантии эффективности.

#algorithm

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

#algorithm

Сравнивая эти два подхода для лабиринта, можно выделить несколько критериев. Для задачи нахождения любого выхода оба алгоритма работают, но DFS требует меньше памяти. Для поиска кратчайшего пути BFS гарантирует результат, а DFS — нет. В глубоких лабиринтах рекурсивный DFS рискует переполнить стек, тогда как итеративный и BFS безопасны. В широких лабиринтах BFS может потребить много памяти, а DFS остается эффективным.

Что касается вычислительной сложности, то и для DFS, и для BFS она одинакова. Временная сложность составляет O(V + E), где V — количество вершин (узлов), а E — количество ребер. Это объясняется тем, что алгоритм посещает каждую вершину ровно один раз и просматривает каждое ребро также один раз. Пространственная сложность в худшем случае составляет O(V) — память нужна для хранения множества посещенных узлов и, в случае итеративной реализации, стека.

Подводя итог, можно сказать, что DFS — это алгоритм, который идет вглубь до упора, а затем возвращается. Его можно реализовать элегантно через рекурсию или более контролируемо через явный стек. Он применяется для поиска любого пути, обнаружения циклов, топологической сортировки и обхода деревьев, но не гарантирует нахождения кратчайшего маршрута.

#algorithm

def bellman_ford(graph, start):
    distances = {node: float("infinity") for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):  # V-1 итераций
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    return distances

Сложность Беллмана–Форда выше — O(V·E), но он способен обнаруживать отрицательные циклы и, соответственно, определять, что задача не имеет решения. Сравним два подхода:

- Дейкстра: работает только с неотрицательными весами, быстрее (O((V+E) log V)).
- Беллман–Форд: работает с любыми весами, медленнее (O(V·E)), может обнаруживать отрицательные циклы.

В реальной жизни алгоритм Дейкстра широко применяется. Например, в GPS-навигаторах (Google Maps, Яндекс.Карты) города или перекрёстки — это вершины, дороги — рёбра, а весом может быть время в пути. Алгоритм находит маршрут с минимальным временем. В интернете протоколы маршрутизации, такие как OSPF, используют алгоритм Дейкстры для определения кратчайшего пути передачи пакетов данных (вершины — роутеры, рёбра — каналы связи, вес — задержка или пропускная способность). В игровых движках NPC (неигровые персонажи) находят путь по карте с препятствиями. В системах поиска авиабилетов вершинами выступают аэропорты, рёбрами — рейсы, а весом — стоимость или время, что позволяет находить самые дешёвые или быстрые маршруты с пересадками.

#algorithm

Другая известная задача, где жадный подход блестяще работает, — это задача о выборе заявок (Activity Selection Problem). Представьте, что у вас есть множество мероприятий, каждое из которых имеет время начала и окончания. Вам нужно выбрать максимальное количество непересекающихся мероприятий, то есть таких, которые не накладываются друг на друга по времени. Жадная стратегия здесь заключается в сортировке всех мероприятий по времени окончания. Логика проста: чем раньше заканчивается текущее мероприятие, тем больше времени остается для всех последующих. Рассмотрим мероприятия: А (1-4), В (2-6), С (5-8), D (7-9) и Е (3-5). Отсортировав их по времени конца, получим последовательность: А(1-4), Е(3-5), В(2-6), С(5-8), D(7-9). Первым мы всегда берем мероприятие, которое заканчивается раньше всех — это А. Его конец в 4. Далее мы пропускаем все мероприятия, которые начинаются раньше или в момент 4 (это Е и В), так как они пересекаются с А. Следующее подходящее — С, начинающееся в 5, что позже 4, поэтому мы берем его. После С с концом в 8, мероприятие D (начало в 7) пересекается с ним и не подходит. В итоге получаем набор из двух мероприятий [A, C], что является максимально возможным количеством. Этот подход работает, потому что задача обладает свойством жадного выбора: мероприятие с самым ранним окончанием всегда входит в какое-либо оптимальное расписание. Это можно строго доказать, показав, что если в оптимальном решении первым стоит не самое раннее мероприятие, его можно заменить на самое раннее, не ухудшив результат. Реализуется алгоритм следующим образом:

Пример 2

Еще одним ярким примером жадного подхода является алгоритм Хаффмана, используемый для сжатия данных. Идея сжатия заключается в том, чтобы представить символы не фиксированным количеством бит (например, 8), а переменным: частым символам давать короткие коды, а редким — длинные. Возьмем строку "aaaaabbc", где 'a' встречается 5 раз, 'b' — 2, а 'c' — 1. При стандартном кодировании каждый символ занял бы 3 бита, и вся строка — 24 бита. Оптимальное кодирование может быть таким: a='0' (1 бит), b='10' (2 бита), c='11' (2 бита). Тогда строка займет всего 5*1 + 2*2 + 1*2 = 11 бит. Алгоритм Хаффмана строит дерево кодирования, где путь от корня до символа определяет его код (0 — переход к левому потомку, 1 — к правому). Его жадная стратегия заключается в следующем: на каждом шаге два символа (или группы символов) с наименьшими частотами объединяются в один узел-родитель, чья частота равна сумме частот потомков. Начнем с отдельных узлов: [a:5], [b:2], [c:1]. На первом шаге выбираем самые редкие — b и c — и объединяем их в узел [bc:3] с двумя потомками. Теперь у нас есть узлы [a:5] и [bc:3]. Снова выбираем два с наименьшей частотой (a и bc) и объединяем их в корень дерева [abc:8]. После этого, двигаясь от корня к листьям и присваивая левым ветвям 0, а правым — 1, мы получим коды: a=0, b=10, c=11. Это жадный алгоритм, так как на каждом шаге мы, не думая о будущей структуре дерева, делаем локально наилучший выбор — объединяем два самых непопулярных элемента, что в итоге и гарантирует минимальную общую длину кода.

Пример 3

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

#algorithm

Важно понимать разницу между динамическим программированием и подходом «Разделяй и властвуй». Оба метода дробят задачу, но делают это по-разному. В «Разделяй и властвуй» подзадачи независимы и не перекрываются — каждая решается отдельно и больше не встречается. Классический пример — сортировка слиянием (Merge Sort), где массив делится на независимые половины, которые сортируются сами по себе и никогда не влияют на вычисление друг друга. В динамическом программировании подзадачи обязательно перекрываются: результат одной и той же маленькой задачи требуется при решении нескольких более крупных. Правило выбора подхода простое: если подзадачи перекрываются — используем ДП, если нет — «Разделяй и властвуй».

Классической задачей на ДП является задача о рюкзаке (Knapsack problem). Представь, что у тебя есть рюкзак вместимостью W и набор из n предметов, каждый из которых имеет свой вес w[i] и ценность v[i]. Цель — набрать предметы так, чтобы их суммарная ценность была максимальной, а суммарный вес не превысил W. Например, при вместимости рюкзака W = 7 и предметах с весами и ценностями (1, 1), (3, 4), (4, 5), (5, 7) лучшим выбором будут предметы 2 и 3 (вес 3+4=7, ценность 4+5=9). Почему это задача ДП? Потому что при решении вопроса «брать или не брать предмет i» мы приходим к подзадачам, которые будут переиспользоваться. Если мы берем предмет, нам нужно решить ту же задачу для оставшихся предметов с вместимостью W - w[i]. Если не берем — для оставшихся предметов с той же вместимостью W. Эти подзадачи постоянно повторяются в разных комбинациях. Решается задача методом табуляции. Мы создаем таблицу dp[i][w], где значение в ячейке — это максимальная ценность, которую можно получить, используя первые i предметов при вместимости рюкзака w. Логика заполнения таблицы такова: если вес текущего предмета больше текущей вместимости w, он просто не помещается, и мы берем значение сверху (без этого предмета): dp[i][w] = dp[i-1][w]. Если же предмет помещается, у нас есть два варианта: не брать его (dp[i-1][w]) или взять, добавив его ценность к оптимальному решению для оставшегося места (dp[i-1][w - w_i] + v_i). Выбираем максимум.

def knapsack(weights, values, W):
    """
    Решение задачи о рюкзаке методом ДП (табуляция).
    
    weights — список весов предметов
    values  — список ценностей предметов
    W       — вместимость рюкзака
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_i = weights[i - 1]
        v_i = values[i - 1]

        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if w_i <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - w_i] + v_i)

    return dp[n][W]


weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7

print(knapsack(weights, values, W))  # 9

Временная сложность этого алгоритма составляет O(n × W), что называется псевдополиномиальной, так как зависит не только от количества предметов, но и от значения вместимости W.

Итак, резюмируя, динамическое программирование — это мощный инструмент, который подходит для задач, обладающих двумя ключевыми свойствами: оптимальной подструктурой (решение большой задачи строится из решений подзадач) и перекрывающимися подзадачами (одни и те же подзадачи решаются многократно). В зависимости от контекста мы можем использовать либо нисходящее рекурсивное решение с кэшированием (мемоизация), либо восходящее итеративное заполнение таблицы (табуляция). Это принципиально отличает ДП от подхода «Разделяй и властвуй», где подзадачи всегда независимы.

#algorithm

Сравнивая эти классы, можно выстроить их от самого быстрого к самому медленному: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Важно помнить, что нотация Big O применяется не только ко времени, но и к памяти — это называется пространственной сложностью (space complexity). Алгоритм может работать очень быстро, но при этом потреблять огромное количество оперативной памяти, и иногда приходится сознательно выбирать: потратить больше памяти ради скорости или наоборот.

Стоит учитывать и несколько важных нюансов. Big O описывает поведение алгоритма при больших n, но это не всегда полная картина: на маленьких объемах данных алгоритм с квадратичной сложностью O(n²) может на практике работать быстрее, чем алгоритм с линейно-логарифмической O(n log n), если у первого значительно меньше константы. Существуют и другие нотации, например Ω (омега), которая описывает лучший сценарий, и Θ (тета), дающая точную оценку. Однако в повседневной практике разработчики, говоря о сложности, почти всегда имеют в виду именно Big O, то есть оценку в худшем случае.

#algorithm