Введение в программирование 1. Асимптотика

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 2 сентября 2021 года
Лектор: Степанов Илья Даниилович
Оператор: Мария Шкатова
Монтаж: Жильцов Игорь

00:00 - Введение
01:14 - O-нотация
03:52 - Критерий f = O(g)
10:33 - Определение Ω и Θ
14:28 - Примеры
20:52 - Мастер-теорема
32:03 - T(n) = 2T(n/2) + Θ(n) ⇒ T = Θ(n log n)
35:01 - Задача 1. Сумма на отрезке
40:39 - Задача 2. Бин. поиск

[tatarin]

Хочу поддержать канал лайком и комментом, чтобы он развивался!

[alexandernefedov]

на 20:05 не понятно почему вдруг (log(n))^10=O(N^(1/5)). скорее имелось в виду, что (log(n^10))=O(N^(1/5))

[freaxlover]

Доску действительно рукожоп сделал.
Спасибо за лекции!

[ybrbnf]

По этому предмету существуют какие-то учебники с похожей структурой подачи курса? Или вся информация только из лекций идёт?

[AnarchySane]

Осталось еще слайды с теорией заранее подготовить, чтобы не тратить на паре на это время.