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

  1. [15 минут] Информация о курсе
    1. Отчётность: по теории экзамен, по практике каждую неделю +1 контест, +1 порция теорзадач
    2. Как сдавать ДЗ: дедлайны жёсткие, контест в систему на c++, теорию в tex в svn (пока на почту)
    3. Обратите внимание на: не нужно списывать, вообще. Если у вас есть вопросы, сложности − обратитесь к преподавателям, к одногруппникам.
    4. Полезные ссылки: wiki , материалы курса алгоритмов , контакты препов
− Перерыв −
  1. [5 минут] Общие слова
    1. Будем оценивать хорошесть алгоритма, время работы, зависит от размера входных данных. Пример − поиск минимума в массиве, O(n).
    2. 3 GHz − 3 000 000 000 операций в секунду (на самом деле меньше, т.к. сложные операции)
    3. Питон − очень медленно (1 000 000 операций в секунду), плюсы − быстро (1 000 000 000 операций в секунду)
    4. Оцениваем время алгоритма в первую очередь примерно, с точностью до константы.

  2. [15 минут] Асимптотика: базовые обозначения, определения, свойства
    1. Определения (O, o, Ω, ω, Θ), уже здесь нужно сказать, что n = O(2n), 2n = O(n), n ≠ o(n), n = o(n2).
    2. Примеры: n и 2n+1, 2n и n2; O(Θ(O(f))), Θ(o(Θ(O(f)))), ...
    3. Свойства (транзитивность, связь определений друг с другом)
    4. Следствия: f ± o(f), nk от nk+1, многочлен от старшего члена.

  3. [10 минут] Примеры
    1. 5 циклов for, n5 / 5! (константа таки важна)
    2. Длинные числа, числа Фибоначчи на самом деле считаются за квадрат (договорённость, какие операции сколько работают)
    3. Найти все a2 + b2 = N двумя циклами (показываем два указателя)
    4. Для всех чисел от 1 до n сгенерить список делителей (nlogn, 2 цикла for, оцениваем сумму гармонического ряда).
− Перерыв −
  1. [15 минут] Умножение многочленов и чисел
    1. Умножение в столбик за O(nm), хранение чисел
    2. Многочлены, числа, переносы
    3. Алгоритм Карацубы за O(n1.58)

  2. [25 минут] Главные теоремы
    1. [15 минут] Рекуррентность: мастер теорема T(n) = aT(n/b) + nc. Доказательство времени работы Карацубы.
    2. [2 минут] Примеры на экспоненциальные соотношения: числа Фибоначчи, оценки 2n и 2n/2
    3. [15 минут] Теорема об экспоненциальных рекуррентных соотношениях T(n) = ∑i bi T(n-ai). Применение к числам Фибоначчи.

  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)

  4. [2 минут] Формулировки: logan = O(nb), na = O(bn)