3AM · электронный учебник для бакалавров

Анализ эффективности алгоритмов

Как посчитать, сколько операций делает алгоритм с циклами или рекурсией, и получить точную формулу и класс эффективности. По книге А. Левитина «Introduction to the Design and Analysis of Algorithms», §2.3–2.5.

2модуля и введение
25вопросов в квизах
26задач с решениями
8интерактивных моделей

Авторы: Калжан Ақниет, Кеңес Маржан, Абильмажитова Алина, Алтыбаева Аружан  ·  Самостоятельная работа «E-Textbook on Algorithm Analysis»

Как пользоваться

Читайте по порядку: введение → модуль 1 → модуль 2. Каждый модуль начинается с целей, затем идут теория и разборы примеров по общему плану, интерактивные модели, квиз и задачи трёх уровней. Заканчивается модуль резюме и шпаргалкой формул. Подчёркнутые пунктиром термины ведут в глоссарий, при наведении показывается короткое определение. На любой раздел и любую задачу можно дать ссылку: значок # рядом с заголовком.

Оглавление

  1. Введение: как измерять эффективность
    Повторение основ перед модулями. Входной квиз из 5 вопросов.
  2. Модуль 1. Анализ нерекурсивных алгоритмов
    Лекция 4, Левитин §2.3, 2.1, 2.6, Приложение A. Циклы превращаются в суммы.
  3. Модуль 2. Анализ рекурсивных алгоритмов
    Лекция 5, Левитин §2.4–2.5, Приложение B, §8.2. Рекурсия превращается в рекуррентное соотношение.
  4. Глоссарий
    Ключевые термины с определениями и ссылками на разделы.
  5. Источники
    Литература, программный код для эмпирической части, использованные инструменты.