Асимптотика (4 сентября 2017)

1. [15 минут] Разбор вступительного теста
2. [15 минут] Информация о курсе, отчётности: контест каждую неделю, теор ДЗ каждую неделю, tex, c++, svn.

1. [15 минут] Базовые обозначения, определения, свойства
1. Определения (O, o, Ω, ω, Θ)
2. Примеры (см. конспект)
3. Следствия: f + o(f), n^k от n^k+1, многочлен от старшего члена.


2. [20 минут] Примеры
1. 5 циклов for, n⁵ / 5!
2. Длинные числа, числа Фибоначчи на самом деле считаются за квадрат
3. Найти все a² + b² = N двумя циклами (показываем два указателя)
4. Для всех чисел от 1 до n сгенерить список делителей (nlogn, 2 цикла for, оцениваем сумму гармонического ряда).

1. [20 минут] Умножение многочленов и чисел
1. Умножение в столбик за O(nm), хранение чисел
2. Многочлены, числа, переносы
3. Алгоритм Карацубы за O(n^1.58)


2. [35 минут] Главные теоремы
1. [15 минут] Рекуррентность: мастер теорема T(n) = aT(n/b) + n^c. Доказательство времени работы Карацубы.
2. [5 минут] Доказательство по индукции на примере T(n) = max_x=1..n-1[T(x) + T(n-x) + x(n-x)].
3. [2 минут] Примеры на экспоненциальные соотношения: числа Фибоначчи, оценки 2ⁿ и 2^n/2
4. [15 минут] Теорема об экспоненциальных рекуррентных соотношениях T(n) = ∑_i b_i T(n-a_i). Применение к числами Фибоначчи.


3. [10 минут] Примеры асимптотик
1. T(n) = 2T(n/2) + n, T(n) = 2T(n/2) + Cn, T(n) = 2T(n/2) + O(n)
2. T(n) = T(n-1) + n
3. T(n) = T(n-3) + T(n-3)
4. T(n) = T(n-1) + T(n-2) + T(n-2)