Алгоритмы и структуры данных

Объяснение

Сложность описывает рост числа операций, а не секунды. Два вложенных цикла по n элементам дают n² итераций; удвоение n увеличивает работу примерно вчетверо. Инвариант — утверждение, истинное до и после каждого шага алгоритма.

Задача для самостоятельного решения

Посчитайте сравнения полного попарного перебора для n=10 и n=20.

Объяснение

Массив даёт доступ по индексу за O(1), но вставка в начало требует сдвига O(n) элементов. Стек извлекает последний добавленный элемент, очередь — первый. Связный список не даёт быстрого поиска по индексу.

Задача для самостоятельного решения

Стек и очередь получили A, B, C. Каков порядок извлечения?

Объяснение

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

Задача для самостоятельного решения

В таблице из 4 корзин h(k)=k mod 4 разместите 2, 6, 9.

Объяснение

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

Задача для самостоятельного решения

Вставьте 1, 2, 3, 4 в обычное дерево поиска.

Объяснение

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

Задача для самостоятельного решения

Для A→B, A→C, B→D, C→D найдите расстояние A–D.

Объяснение

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

Задача для самостоятельного решения

Монеты 1, 3, 4: сколько монет нужно для суммы 6?

Подготовка

Python 3. Сохраните код и выполните локально.

Учебный пример

from collections import deque

def distance(graph, start):
    result = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor not in result:
                result[neighbor] = result[node] + 1
                queue.append(neighbor)
    return result

assert distance({"A":["B","C"],"B":["D"],"C":["D"]}, "A")["D"] == 2
assert distance({"A":["A"]}, "A") == {"A":0}
print("OK")

Как работает пример и что ожидать

Результат OK. result одновременно хранит расстояние и отмечает посещённость. Вершина помечается до помещения в очередь, поэтому петля A→A не создаёт бесконечный обход. Каждая вершина и ребро рассматриваются ограниченное число раз: O(V+E) времени и O(V) дополнительной памяти.

Итоговая работа

Добавьте восстановление пути через parent, тест недостижимой вершины и цикл из трёх вершин. Сравните BFS с поиском глубиной на графе, где первый найденный путь не кратчайший. Затем реализуйте двоичный поиск, heap и DP для монет с тестами границ.

Проверка результата

1. Опишите исходные данные и условия запуска, чтобы другой человек мог повторить работу.
2. Приложите результат обычного сценария и сравните его с ожидаемым.
3. Проверьте неверный вход, граничный случай и отказ зависимости, если она есть.
4. Объясните выбранное решение и известное ограничение.
5. Сохраните исправления после самопроверки вместе с примером, который раньше не работал.

Как оценить работу

По каждому пункту поставьте 0 (не выполнено), 1 (выполнено с пробелами) или 2 (результат воспроизводим и объяснён). Если обязательный сценарий не работает, вернитесь к нему независимо от общей суммы. Это рубрика самопроверки: сайт не исполняет присланный код и не выдаёт автоматическую оценку проекта.