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

1. Рекуррентность
1. [10 минут] Доказательство мастер-теоремы
2. [1 минут] Обобобщение мастер-теоремы T(n) = aT(n/b) + n^clog^dn
3. [5 минут] Доказательство по индукции на примере T(n) = max_x[T(x) + T(n-x) + x(n-x)]. Как догадаться до ответа?
4. [2 минут] Примеры на экспоненциальные соотношения: числа Фибоначчи, оценки 2ⁿ и 2^n/2
5. [15 минут] Теорема об экспоненциальных рекуррентных соотношениях T(n) = ∑_i T(n-a_i)
2. [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)

1. [15 минут] Примеры на асимптотику (оценка сверху и снизу, Θ)
1. Числа Фибоначчи за линию
2. Длинные числа, числа Фибоначчи на самом деле считаются за квадрат
3. Найти все a² + b² = N двумя циклами
4. 5 циклов for, n⁵ / 5!
5. Для всех чисел от 1 до n сгенерить список делителей (nlogn, 2 цикла for)
2. [15 минут] Интегралы
1. Определение интеграла, связь с суммой
2. Мы умеем дифференцировать! log'(x) = 1/x, (xⁿ)^' = nx^n-1
3. Другое доказательство времени для примера со списком делителей
3. [20 минут] Ещё про асимптотики
1. Определение O и o через пределы
2. [homework] f + o(f) = Θ(f)
3. log^an = O(n^b)
4. n^a = O(bⁿ)
5. Следствие: не только O-большое, но и o-маленькое