Анализ производительности алгоритмов

— М.: Изд. Дом Вильямс, 2000. — 960 с.
Ахо А., Хопкрофт

Д., Ульман Д. Структуры данных и алгоритмы. – М.: Изд. Дом Вильямс, 2000. – 384с.
Кнут Д. Искусство программирования, т.1 Основные алгоритмы, Изд. Дом Вильямс, 2000. – 384с.

с англ. — М. : Издательский дом "Вильяме", 2006. —

576 с.
Дж. Макконнелл Основы современных алгоритмов. 2-е издание. М.: Техносфера, 2004. - 368с.

раздел теории алгоритмов – теория сложности вычислений
Для программиста теория сложности

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

памяти при увеличении входных данных.
Время (память), затраченное алгоритмом, как функция

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

1
Для каждого слагаемого, кроме a0 возвести x в заданную степень

последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить.
Вычисление i-го слагаемого (i=1..n) требует i умножений.
всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений.
кроме того, требуется n+1 сложение.
Всего n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операций.

Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0

внутренняя скобка требует одно умножение и одно сложение. Ее значение

используется для следующей скобки.
И так, одно умножение и одно сложение на каждую скобку, которых n-1 штука.
И еще после вычисления самой внешней скобки умножить на x и прибавить a0.
Таким образом, всего n умножений и n сложений, всего 2n операций.

Pn(x) = a0 + x(a1 + x(a2 + ... ( ai + .. x(an-1 + anx)))

данных получили обозначения с использованием символа О(*).
Типичный результат:
сложность алгоритма

сортировки – О(nlogn). Читается как «сложность алгоритма порядка nlogn»
это следует понимать так: существует константа C > 0, такая, что время работы алгоритма в худшем случае не превышает C·n·log2n.
Существует и другой подход, который заключается в рассмотрении сложности в среднем.

увеличением размерности, т.е.алгоритм, работающий за время О(nlogn) лучше алгоритма с

временем работы О(n2).
Таким образом, сложность алгоритма определяется как порядок функции, выражающее время его работы или затрачиваемую память.