Анализ алгоритмов
При анализе алгоритмов мы должны обращать внимания на многие вещи: простота реализации, безопастность, возможность переиспользования и т.д. Однако основным аспектом любого алгоритма является затраченные на его выполнения ресурсы к которым относятся время и память.
Анализировать затраченное на выполнение алгоритма время можно двумя принципиально различными способами: экспериментально и теоретически.
Эксперементальный анализ
Для того, чтобы получить эксперементальную оценку времени выполнения нам необходимо выполнить следущие шаги:
- Реализовать алгоритм на одном из языков программирования;
- Запустить программу на различных входных данных (варьируя размер входных данных);
- Используя такой класс, как Stopwatch (System.currentTimeMillis), замерить фактическое время работы алгоритма;
- Опционально, изобразить полученный набор данных (см. рисунок)
Такой подход измерения времени работы алгоритма имеет ряд недостатков:
Необходимо реализовать и протестировать алгоритм для того, чтобы определить время его работы;
Эксперименты можно сделать только на ограниченном наборе входных данных, то есть они могут не точно говорить о времени работы алгоритма на других входных данных которые не включенны в эксперимент;
Время работы алгоритмов может зависить от компьютера на котором они выполняются, то есть для того, чтобы сравнить два алгоритма, необходимо использовать одинаковые аппаратные и программные среды.
Для решения недостатков эксперементального анализа был разработан теоретический анализ.
Теоретический анализ
В отличии от эксперементального, теоретический анализ:
- Использует высокоуровневое описания алгоритма вместо его реализации;
- Характеризует время работы агоритма как функцию зависящую от размера входных данных $$n$$;
- Принимает во внимание все возможные входные данные;
- Позволяет оценить скорость работы алгоритма вне зависимости от программного и аппаратного обеспечения.