Критерии эффективности и сложность алгоритмов

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

а) время выполнения алгоритма (количество шагов)

б) объем памяти необходим для выполнения вычислений.

Оценки времени выполнения алгоритмов в общем случае вычисляются достаточно сложно.

Пусть для алгоритма нахождения НОД поставлена задача:

n – известно, а m – любое целое положительное число, такое что m≤n.

Определить: сколько в среднем раз (Т_n) выполняется шаг Ш1 при достаточно большом n.

Очевидно, чтобы найти среднее Т_n необходимо испытать алгоритм для m=1, m=2, m=3, …, m=n и подсчитать при этом суммарное число выполнений Ш1 и разделить на n

Было доказано что для больших значений n: , т.е. пропорционально ln(n) с коэффициентом пропорциональности , который без испытаний и проведений определенных вычислений угадать невозможно.

Объем памяти, необходимый для проведения вычислений может увеличивать или уменьшать время выполнения алгоритма. Увеличение происходит при нехватке памяти => не имеем мощного компьютера - выбираем сложный алгоритм.

Формально любой алгоритм опр. Как некоторый вычислительный метод, представляющий собой некую четверку (Q,I,W,f)

Q- все возможные допустимые состояния вычислений при работе алгоритма.

I - все множество допустимых входящих данных алгоритма

W - все множество выходных результатов.

F - правило вычислений в алгоритме, которое может быть очень сложным и состоять из многих действий.

Сложность алгоритма определяется:

1-время выполнения алгоритма

2-Необходимый объем памяти для вычисления

3-общее количеством шагов в алгоритме

4-вместо общего числа шагов можно подсчитывать кол-во шагов определенного вида(например число арифметических операций при вычислении выражения)
7. Классификация задач по степени сложности.

Сложность задачи определяется через сложность наилучшего алгоритма, известного для ее решения.

Быстрыми алгоритмами являются линейные, которые обладают сложностью порядка n, и называются алгоритмами порядка 0(n), где n – размерность входного данного.

К линейным алгоритмам относятся:

алгоритм нахождения суммы для типичных чисел, состоящих из n₁ и n₂ цифр. Его сложность 0(n₁)+n₂.

Есть более быстрые алгоритмы, чем линейные. Например, алгоритм двоичного поиска в линейном упорядоченном массиве, его сложность 0(log₂n), где n – длинна упорядоченного массива.

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

Полиномиальные алгоритмы – алгоритмы, принадлежащие классу Р, эти алгоритмы имеют полиномиальную временную сложность и в общем виде их сложность записывается 0(n^к), где к из Z, k>0.

Алгоритмы для которых не существует такой временной оценки – экспоненциальные. Задача, считается трудно решаемой. Если для нее не существует решающего эту задачу полиномиального алгоритма.

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

Класс Р: Задачу называем «хорошей» если для нее существует полиномиальный алгоритм (Рассоривать множество из n чисел(сложность 0(n²)), нахождение вершин, связанных цепочкой дуг(0(n+m)) и т.п.)

Класс Е:

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

Ни Р ни Е:

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