Роль алгоритмов в работе физика
Устройство Python было рассмотрено в предыдущем разделе, однако за ним стоит фундамент, переживающий и смену языка, и смену моды, — базовые знания computer science.
Алгоритмическая грамотность представляет собой умение заранее оценить, выполним ли расчёт за приемлемое время. Миллион событий детектора, обрабатываемый алгоритмом за \(O(n^2)\), приводит к триллиону операций, и NumPy, написанный на C, в этом случае не поможет. Удачно выбранная структура данных сокращает время счёта на порядки, причём чаще, чем низкоуровневая оптимизация.
В настоящем разделе рассматриваются:
- Введение в алгоритмы, где вводится понятие алгоритма и разбирается оценка сложности, не привязанная к конкретной машине;
- Основные структуры данных, где разобраны массивы, списки, стеки, очереди и деки и показано, как они представлены в Python;
- Рекурсия и сортировки, где разобраны сортировка слиянием, быстрая сортировка и сортировка подсчётом;
- Хеш-функции, объясняющие, почему словарь ищет за \(O(1)\) и как устроены хеш-таблицы;
- Деревья, иерархические структуры, дополненные деревьями поиска и кучами;
- Графы, их представления, обходы и классические задачи, решаемые обходом.
Материал построен на разборе задач: сначала излагается необходимая теория, затем приводятся задачи с решениями, расписанными на Python. Рекомендуется сперва попытаться решить задачу самостоятельно и только после этого обращаться к разбору.