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

  1. [15 минут] Разбор вступительного теста
  2. [15 минут] Информация о курсе, отчётности
  3. [15 минут] Асимптотика: определения (O, o, Ω, ω, Θ)
− Перерыв −
  1. [15 минут] Асимптотика
    1. Следствия
    2. Примеры
    3. Многочлен − Θ от старшего члена
  2. [20 минут] Умножение чисел
    1. Умножение в столбик за O(nm), хранение чисел
    2. Многочлены, числа, переносы
    3. Алгоритм Карацубы за O(n1.58)
  3. [15 минут] Рекуррентность: мастер теорема T(n) = aT(n/b) + nc