Анализ алгоритмов

Принципиальной альтернативой математическому анализу эффективности алгоритмов является их эмпирический анализ.

Имеется ряд целей, которые могут быть поставлены перед эмпирическим анализом алгоритмов. Они включают проверку точности теоретических выводов об эффективности алгоритма, сравнение эффективности нескольких алгоритмов, предназначенных для решения одной и той же проблемы или различных реализаций одного и того же алгоритма, выдвижение гипотезы о классе эффективности алгоритма, выяснение эффективности программы, реализующей алгоритм, на данной конкретной машине.

Главное преимущество математического анализа – его независимость от конкретных входных данных, а недостаток – ограниченная применимость, в особенности для исследования эффективности в среднем случае. Эмпирический анализ, напротив, применим к любому алгоритму, но его результаты могут зависеть от конкретных входных данных и использованного для проведения эксперимента компьютера.

Общий план эмпирического анализа эффективности алгоритма

1. Уяснение цели предстоящего эксперимента.
2. Определение измеряемой метрики М и единиц измерения (количество операций или время работы).
3. Определение характеристик входных данных (их диапазон, размер и т.д.).
4. Создание программы, реализующей алгоритм (или алгоритмы), для проведения эксперимента.
5. Генерация образца входных данных.
6. Выполнение алгоритма (или алгоритмов) над образцом входных данных и запись наблюдаемых данных.
7. Анализ полученных данных.

Цель эксперимента должна влиять, если не определять, на то, каким образом будет выполняться измерение эффективности алгоритма.

Для подсчёта количество выполнений алгоритмом базовых операций в программу, реализующую алгоритм, вставляется счетчик.

Для определении времени работы программы можно определять время работы фрагмента кода, запрашивая системное время непосредственно перед началом выполнения фрагмента (`t_{"start"}`) и сразу после его завершения (`t_{"finish"}`), а затем просто вычислять разность полученных значений (`t_{"finish"} - t_{"start"}`). Определение времени обычно не очень точное, и можно получить несколько отличающиеся друг от друга результаты при повторных запусках одной и той же программы с одними и теми же входными данными. Регистрируемое время может включать время, затраченное процессором на работу над другими программами, что также снижает точность эксперимента.

Таким образом, измерение физического времени работы имеет ряд недостатков, которых нет у метода подсчета базовых операций. С другой стороны, измерение физического времени дает очень конкретную информацию о производительности алгоритма в данной вычислительной среде, что для экспериментатора может оказаться более важным, чем класс асимптотической эффективности алгоритма. Кроме того, измерения времени, затраченного на различные части программы, могут помочь выявить узкие места в производительности программы, что не позволит сделать абстрактное рассмотрение базовых операций алгоритма. Получение таких данных, которое называется профилированием; обычно в большинстве сред имеются специальные системные инструменты для получения данной информации.

Независимо от метода измерения производительность алгоритма, перед вами встанет вопрос о выборе образца исходных данных для проведения эксперимента. Зачастую требуется использовать образец входных данных, представляющий собой "типичные" данные. Для некоторых классов алгоритмов, например, алгоритмов для решения задачи коммивояжера, исследователи разработали наборы тестовых образцов. Однако на практике гораздо чаще приходится сталкиваться с ситуациями, когда входные данные должен выбирать и готовить сам экспериментатор. Обычно приходится самостоятельно решать, каков должен быть размер входных данных (разумно начать с данных относительно небольшого размера и при необходимости постепенно увеличивать их), диапазон величин входных данных (чтобы он не был ни слишком малым, ни слишком большим), и разрабатывать процедуру для генерации входных данных в выбранном диапазоне.

Эмпирические данные, полученные в ходе эксперимента, должны быть записаны, а затем представлены для дальнейшего анализа. Данные могут быть представлены в таблице или графически, точками в декартовой системе координат. Неплохая мысль использовать одновременно оба способа, поскольку для каждого из них характерны свои сильные и слабые стороны.

Одно из возможных применений эмпирического анализа – попытка предсказать производительность алгоритма для экземпляра исходных данных, не включенного во множество экземпляров исходных данных эксперимента. Например, если мы заметим, что отношение `(T(n))/(g(n))` близко к некоторой константе `c` для экземпляров, использованных в эксперименте, то мы можем аппроксимировать `T(n)` произведением `c g(n)` и для других значений `n`.

Задания для практики

Определите класс эффективности алгоритма на основании времени выполнения программы: