2. Алгоритмы и их анализ
Пошаговые инструкции и их «цена» (скорость и память). Фундамент эффективных вычислений.
2. Алгоритмы и их анализ
Алгоритмы сортировки
Сортировка — базовая задача CS. QuickSort (1959) работает за O(n log n), BubbleSort за O(n²). TimSort используется в Python и Java по умолчанию.
Алгоритмы поиска
Бинарный поиск — O(log n): из 1 млн элементов за 20 шагов. Линейный — O(n): 1 млн шагов. Дейкстра и A* находят кратчайший путь в графах. Основа баз данных и навигаторов.
Методы проектирования
Динамическое программирование, мемоизация и жадные алгоритмы. Парадигмы построения эффективных решений.
Теория сложности
Теория вычислительной сложности изучает ресурсы, необходимые для решения задач, прежде всего время и память. Класс NP включает задачи распознавания с полиномиальной проверкой свидетельства положительного ответа; принадлежность к NP сама по себе не доказывает неполиномиальную трудность.