Практика языка C (МФТИ, 2023-2024). Семинар 3.2. Стратегия “разделяй и властвуй“.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики. На этом занятии мы плотно займёмся анализом алгоритмов. Начнём мы с бинарного поиска и сортировок, использующих стратегию разбиения пополам. А дальше погрузимся в доказательство основной теоремы (master theorem) которую далее будем использовать в анализе асимптотической сложности. Я попробую не только доказать эту теорему но и объяснить как она работает. Ну а закончим поучительным перемножением полиномов. Семинарист: Константин Владимиров. Дата: 3 ноября 2023 года. Съёмка: Марк Гончаров. Звук: Юлий Тарасов. Предыдущий семинар: Следующий семинар: Слайды к занятиям: Примеры кода: Задачник: Timeline 00:00 Вступление 02:45 Линейный и бинарный поиск 10:35 Быстрая сортировка 17:45 Разбиение по элементу 24:20 Сортировка слиянием 28:40 Основная теорема 50:40 Время решать задачи 52:10 Перемножение полиномов 01:06:10 Ревью кода 01:16:38 Пишем partition 01:26:38 Завершение Errata: * Пока пусто