Справочник

Источники

Литература

Levitin A. Introduction to the Design and Analysis of Algorithms, 3rd ed. Pearson, 2012. Разделы 2.1–2.6, 8.2 (memory functions), Приложения A и B. Основной источник: все определения, формулы и обозначения учебника согласованы с этой книгой.
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, 4th ed. MIT Press, 2022. Главы 3, 4, Приложение A; задачи главы 7 о глубине стека и устранении хвостовой рекурсии.
Sedgewick R., Wayne K. Algorithms, 4th ed. Addison-Wesley, 2011. Раздел 1.4 (эмпирический анализ, тест удвоения).
Kleinberg J., Tardos É. Algorithm Design. Pearson, 2005. Главы 2, 5.
Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics, 2nd ed. Addison-Wesley, 1994. Главы 1, 2, 7 (суммы, рекуррентности, Ханойская башня).
Лекция 4. Математический анализ нерекурсивных алгоритмов (материалы курса).
Лекция 5. Математический анализ рекурсивных алгоритмов (материалы курса).

Программный код

Эмпирическая часть написана на Python и лежит в папке code/ репозитория github.com/rniwd/algorithm-analysis-textbook. Для запуска нужен Python 3 и matplotlib:

python3 -m pip install matplotlib
cd code
python3 run_all.py            # все скрипты со счётчиками
python3 verify_answers.py     # проверка всех числовых ответов задач и квизов

Файл	Что проверяет
`m1_max_element.py`	MaxElement: $C(n) = n - 1$
`m1_unique_elements.py`	UniqueElements: оба худших входа $\frac{n(n-1)}{2}$, лучший $1$
`m1_matrix.py`	матрицы: $M(n) = A(n) = n^3$
`m1_binary.py`	Binary: $\lfloor\log_2 n\rfloor + 1$; цикл $i \leftarrow 2i$
`m1_sequential_search.py`	средний случай $\frac{p(n+1)}{2} + n(1-p)$
`m1_selection_sort.py`, `m1_upper_sum.py`, `m1_dependent_loops.py`	свои примеры модуля 1 и циклы с зависимой границей
`m2_factorial.py`, `m2_hanoi.py`, `m2_binrec.py`, `m2_fibonacci.py`	разборы модуля 2
`m2_rec_max.py`, `m2_fast_pow.py`, `m2_rec_sum.py`	свои примеры модуля 2, лимит рекурсии в Python
`tasks/m1_e1_triple_loop.py`, `tasks/m2_e1_split.py`	решения эмпирических задач
`verify_answers.py`	все числовые ответы задач и квизов сайта

Графики из этих скриптов показаны в разделах эмпирической проверки модуля 1 и модуля 2.

Инструменты

Формулы набраны с помощью KaTeX, подсветка кода — highlight.js. Визуализации написаны на чистом JavaScript и SVG без библиотек.
Графики эмпирической части построены в matplotlib.
Сайт статический, работает на GitHub Pages и при открытии index.html с диска; прогресс квизов хранится только в вашем браузере.

Использование ИИ

При подготовке учебника использовался ассистент Claude Code: черновики текста, псевдокода, задач, визуализаций и скриптов. Все определения и формулы сверены с книгой Левитина. Числовые ответы проверены программой verify_answers.py, решения проверены участниками группы вручную. Подробности — в отчёте группы.