Алгоритмы
Алгоритм — конечная последовательность однозначных шагов, которая для допустимого входа дает требуемый результат. Для заметок важны четыре свойства:
- контракт входа и выхода;
- инвариант — что остается истинным после каждого шага;
- доказательство завершения и корректности;
- время и дополнительная память.
Оценка
- Оценка сложности алгоритмов — практический разбор циклов и структур данных;
- Оценка асимптотической сложности алгоритмов —
O,Ω,Θ, worst/average/best; - Big O — памятка по порядкам роста.
Основные техники
- Рекурсия;
- Жадные алгоритмы;
- divide and conquer — merge sort, quicksort, binary search;
- динамическое программирование — хранение решений перекрывающихся подзадач;
- Map-reduce — независимое преобразование и объединение.
Сортировка
| Алгоритм | Среднее время | Худшее | Доп. память | Стабильность |
|---|---|---|---|---|
| Пузырьковая сорировка | O(n²) | O(n²) | O(1) | да |
| Сортировка слиянием | O(n log n) | O(n log n) | O(n) | да |
| Быстрая сортировка | O(n log n) | O(n²) | стек в среднем O(log n) | обычно нет |
Поиск и структуры
На собеседовании
- Что сначала уточнить у алгоритмической задачи? Размер, диапазон, сортировка входа, дубликаты, mutability и требуемый результат.
- Что такое инвариант? Утверждение, истинное до и после каждой итерации.
- Почему Big O недостаточно? Она не показывает константы, память, локальность, распределение входов и ограничения.
- Как проверить решение? Пустой вход, один элемент, дубликаты, границы диапазона, уже лучший и худший порядок.