Начало
Учебные материалы
Основы анализа алгоритмов
Эффективность алгоритмов Оценка размера входных данных Единицы измерения времени выполнения алгоритма Порядок роста Эффективность алгоритма в разных случаях
Единицы измерения времени выполнения алгоритма
воспользоваться общепринятыми единицами измерения времени --
секундой, миллисекундой и т.д. Однако у такого подхода существуют явные
недостатки, поскольку результаты измерений будут зависеть от:
* быстродействия конкретного компьютера;
* тщательности реализации алгоритма в виде программы;
* типа компилятора, использованного для генерации машинного кода;
* точности хронометрирования реального времени выполнения программы.
--
Поскольку перед нами стоит задача измерения эффективности алгоритма,
а не реализующей его программы, мы должны воспользоваться такой системой
измерений, которая бы не зависела от приведенных выше посторонних факторов.
Один из возможных способов решения этой проблемы состоит в подсчете
того, сколько раз выполняется каждая операция алгоритма. Однако подобный подход
слишком сложен и чаще всего не нужен. Достаточно рассмотреть список наиболее важных операций, выполняемых в
алгоритме, называемых основными, или *базовыми операциями*,
определить, какие из них вносят наибольший вклад в общее время выполнения
алгоритма, и вычислить, сколько раз эти операции выполняются.
--
Обычно в него включают наиболее длительные по времени операции,
выполняемые во внутреннем цикле алгоритма. Например, в алгоритме
сортировки основной является операция
сравнения ключей. В алгоритме
перемножения матриц используются две основные операции: умножение и сложение.
Таким образом, временную эффективность
алгоритма можно оценить по количеству
основных операций, которые должен выполнить алгоритм при обработке
входных данных размера `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`, соответствующего определению этой операции.
