Краткие теоретические сведения
Существует три основные формы сложности алгоритмов: пространственная (объем занимаемой памяти), временная (быстродействие) и интеллектуальная (понятность, лаконичность).
Пространственная сложность измеряется количеством ячеек памяти, требуемых для выполнения алгоритма.
Временная сложность определяется количеством шагов алгоритма (временем), необходимым для выполнения алгоритма.
При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки.
Оценить временную сложность алгоритмов на лабиринтах бывает довольно трудно. Объясняется это тем, что теоретические оценки являются качественными, т.е. дают числовые значения верхней и нижней границы временной сложности с точностью до порядков. В свою очередь, экспериментальные оценки дают точные значения только для конкретных исходных данных, и при изменении исходных данных могут непредсказуемо и значительно изменяться.
Теоретическая оценка сложности алгоритмов состоит в сопоставлении их порядков сложности. Порядок сложности алгоритма (порядок алгоритма) определяется через количество обрабатываемых данных, например через размер вектора n. Если время выполнения алгоритма увеличивается во столько же раз, во сколько раз увеличивается длина вектора, то это значит, что временная сложность носит линейный характер.
Для математического описания порядка сложности алгоритма используются О-функции. О-функция выражает относительную скорость алгоритма в зависимости от некоторой переменной n и выражается через доминирующую функцию.
|
|
|
В зависимости от вида О-функции алгоритмы принято делить на следующие классы сложности:
- O(1) - константная сложность;
- O(хa) - полиномиальная сложность;
- O(Log2(x)) - логарифмическая сложность;
- O(аx) - NP -сложность (экспоненциальная сложность или сложность выше полиномиальной).
Существуют три важных правила для определения сложности.
1. O(k*f)=O(f)
2. O(f*g)=O(f)*O(g) или O(f/g)=O(f)/O(g)
3. O(f+g) равна доминанте O(f) и O(g)
Здесь k обозначает константу, a f и g - функции.
Первое правило означает, что постоянные множители не имеют значения для определения порядка сложности: 1,5*N=O(N)
Из второго правила следует, что порядок сложности произведения двух функций равен произведению их сложностей: O((17*N)*N) = O(17*N)*O(N) = O(N)*O(N)=O(N*N) = O(N2)
Из третьего правила следует, что порядок сложности суммы функций определяется как порядок доминанты первого и второго слагаемых, т.е. выбирается наибольший порядок: O(N5+N2)=O(N5)
Кроме временной сложности алгоритмов существуют и другие меры сложности. Так, сложность можно характеризовать числом операций N (применительно к конкретной ЭВМ) и общим объемом информации Р, т.е общим количеством слов, используемых при выполнении алгоритма (емкостная сложность алгоритма). Тогда время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значение Т называют вычислительной сложностью алгоритма.
|
|
|
Дата добавления: 2016-01-03; просмотров: 12; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!