Алгоритмы и сложность¶
Справочник для самопроверки: краткие ответы на ключевые вопросы по алгоритмам и оценке их сложности.
1. Понятие алгоритма¶
Алгоритм — это конечная последовательность точно определённых действий (шагов), которая по входным данным за конечное число шагов приводит к искомому результату. Это формальное описание способа решения задачи, не зависящее от конкретного исполнителя — человека, языка программирования или железа. Один и тот же алгоритм сортировки можно реализовать и на Python, и на Go.
2. Свойства алгоритма (дискретность, детерминированность, конечность, массовость, результативность)¶
Классический набор свойств: дискретность — алгоритм состоит из отдельных завершённых шагов; детерминированность (определённость) — каждый шаг однозначен, при одинаковых входных данных результат всегда один и тот же; конечность — алгоритм завершается за конечное число шагов; массовость — применим к целому классу однотипных задач, а не к одному частному случаю; результативность — даёт конкретный результат (в том числе сообщение о невозможности решения). Нарушение конечности — это «зависание»: бесконечный цикл вместо ответа.
3. Формы записи алгоритмов (словесная, блок-схема, псевдокод, программа)¶
Словесная — описание шагов на естественном языке (просто, но неточно и громоздко). Блок-схема — графическое представление со стандартными фигурами (ромб — ветвление, прямоугольник — действие), наглядно показывает поток управления. Псевдокод — формализованная запись, близкая к языку программирования, но без строгого синтаксиса; удобна для проектирования. Программа — исполняемая реализация на конкретном языке (Python, Go), единственная форма, которую напрямую выполняет машина.
4. Принципы построения алгоритмов (последовательная детализация, модульность, структурность)¶
Последовательная детализация (нисходящее проектирование, top-down) — задача разбивается от общего к частному: сначала крупные шаги, затем их уточнение. Модульность — разбиение на самостоятельные блоки (функции, процедуры), которые решают подзадачи и переиспользуются. Структурность — построение программы только из трёх базовых конструкций (следование, ветвление, цикл) без хаотичных переходов goto, что делает код читаемым и проверяемым.
5. Основные алгоритмические конструкции (следование, ветвление, цикл)¶
Согласно теореме о структурном программировании любой алгоритм выражается тремя конструкциями: следование — шаги выполняются строго друг за другом; ветвление — выбор одной из ветвей по условию (if/elif/else, match); цикл — повторение блока, пока истинно условие (while) или по элементам коллекции (for). В Go аналогично: единственный цикл for покрывает все варианты, а ветвление — if и switch.
6. Определение сложности работы алгоритмов. O-нотация¶
Сложность оценивает, как растут затраты алгоритма при увеличении размера входа n: временная — число операций, пространственная — объём дополнительной памяти. O-нотация (big-O) описывает асимптотику в худшем случае, отбрасывая константы и младшие члены: важна скорость роста, а не точное число шагов. Чем медленнее растёт функция, тем лучше масштабируется алгоритм.
| Класс | Название | Пример |
|---|---|---|
| O(1) | константная | доступ к элементу массива по индексу, чтение из dict |
| O(log n) | логарифмическая | бинарный поиск в отсортированном массиве |
| O(n) | линейная | проход по списку, линейный поиск |
| O(n log n) | линейно-логарифмическая | эффективные сортировки (merge sort, quicksort) |
| O(n²) | квадратичная | вложенные циклы, пузырьковая сортировка |
7. Принцип «Разделяй и властвуй» (Divide and Conquer)¶
«Разделяй и властвуй» — стратегия, при которой задача рекурсивно разбивается на несколько подзадач того же типа, каждая решается отдельно, а затем результаты объединяются в общий ответ. Три шага: деление (divide) задачи на части, рекурсивное решение (conquer) подзадач, объединение (combine) их результатов. Классические примеры: сортировка слиянием (делим массив пополам, сортируем половины, сливаем) и быстрая сортировка (разбиваем по опорному элементу) — обе дают O(n log n); бинарный поиск на каждом шаге отбрасывает половину диапазона, давая O(log n).
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:]) # делим и решаем
return merge(left, right) # объединяем