Основы анализа алгоритмов

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

• быстродействия конкретного компьютера;
• тщательности реализации алгоритма в виде программы;
• типа компилятора, использованного для генерации машинного кода;
• точности хронометрирования реального времени выполнения программы.

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

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

Обычно в него включают наиболее длительные по времени операции, выполняемые во внутреннем цикле алгоритма. Например, в алгоритме сортировки основной является операция сравнения ключей. В алгоритме перемножения матриц используются две основные операции: умножение и сложение.

Таким образом, временную эффективность алгоритма можно оценить по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера `n`.

Предположим, что `t_{ор}` – время выполнения основной операции алгоритма на конкретном компьютере, а `C(n)` – количество раз, которые эта операция должна быть выполнена при работе алгоритма. Тогда время выполнения программной реализации этого алгоритма на данном компьютере `T(n)` можно приблизительно определить по следующей формуле:
`T(n) ~~ t_{op}*C(n)`.

В значении счетчика `C(n)` не учитывается количество выполняемых алгоритмом операций, не относящихся к основным. Кроме того, обычно значение этого счетчика также можно определить только приблизительно. Более того, значение константы `t_{op}` также можно определить лишь приблизительно и оценить ее точность весьма непросто. Тем не менее, эта формула дает приемлемую оценку времени выполнения алгоритма для не бесконечно больших и не бесконечно малых значений `n`.

Пусть, `C(n) =(n*(n -1))/2`. Насколько дольше будет выполняться программа, если удвоить размер входных данных? Ответ будет такой: приблизительно в четыре раза медленнее. В самом деле, для достаточно больших `n` справедлива следующая формула:
`C(n) = 1/2 n(n-1) = 1/2 n^2 - 1/2 n ~~ 1/2 n^2`.

Поэтому
`{T(2n)}/{T(n)} ~~ {t_{op}*C(2n)}/{t_{op}*C(n)} ~~ { 1/2 (2n)^2}/{ 1/2 n^2} = 4`

Обратите внимание, что для ответа на вопрос не нужно знать реальное значение `t_{op}`, поскольку в приведенной выше дроби оно сокращается. Обратите также внимание, что постоянный множитель `1/2` в формуле для `C(n)` тоже сокращается. По этим причинам в процессе анализа эффективности при достаточно больших размерах входных данных не учитывают постоянные множители, а сосредотачиваются на оценке порядка роста количества основных операций с точностью до постоянного множителя.

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

1. Для каждого из приведенных ниже алгоритмов определите: 1) естественные единицы измерения размера входных данных; 2) основную операцию алгоритма; 3) будет ли изменяться количество основных операций, выполняемых алгоритмом, в зависимости от используемого набора входных данных одинакового размера.
   а) Вычисление суммы `n` чисел.
   б) Вычисление `n!`.
   в) Поиск наибольшего элемента в списке из `n` чисел.
   г) Алгоритм Евклида.
   д) Решето Эратосфена.
   е) Алгоритм умножения в столбик двух n-разрядных десятичных целых чисел.
2. Рассмотрите алгоритм сложения двух матриц размером `n xx n`, основанный на определении сложения матриц. Назовите его основную операцию. Определите зависимость количества основных операций как функцию от порядка матрицы `n`. Найдите зависимость количества основных операций как функцию от числа элементов в матрицах.
3. Выполните аналогичное упражнение для алгоритма умножения двух матриц размером `n xx n`, соответствующего определению этой операции.