Алгоритмы

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

Свойства алгоритма

• Конечность — работа завершается за конечное число шагов.
• Определенность — каждый шаг понятен однозначно, без «на глаз».
• Результативность — для допустимых входных данных получается ответ.

Почему важна сложность

Одну задачу можно решить разными алгоритмами, и разница в скорости бывает огромной. Найти число в упорядоченном списке из миллиона элементов можно перебором — до миллиона сравнений. А можно двоичным поиском: смотреть в середину и каждый раз отбрасывать половину списка — хватит 20 сравнений.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        middle = (low + high) // 2
        if items[middle] == target:
            return middle
        if items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

Рост времени работы описывают O-нотацией: перебор — O(n), двоичный поиск — O(log n). На маленьких данных разницы не видно, на больших она решает все.

Классические задачи и алгоритмы

• Сортировка. Быстрая сортировка и сортировка слиянием упорядочивают n элементов примерно за n·log n шагов.
• Поиск. Двоичный поиск, поиск по хеш-таблице, поиск подстроки в тексте.
• Графы. Алгоритм Дейкстры находит кратчайший путь — так работают навигаторы; обход в ширину ищет связи между объектами.
• Динамическое программирование. Задача разбивается на подзадачи, а их решения запоминаются, чтобы не считать повторно.
• Сжатие и шифрование. Отдельные семейства алгоритмов, на которых держатся архивы и шифрование.

Алгоритмы в бизнес-системах

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