17. Сложноть алгоритмов. Временная и пространственная сложности алгоритмов. Полиномиальные и экспоненциальные алгоритмы.

Обычно эффективность алгоритмов понимается в двух аспектах: по времени решения задачи и по объему требуемой для ее решения памяти. Поэтому говорят о временной сложности алгоритма (ВСА) и сложности в смысле требуемой памяти, иначе, пространственной сложности алгоритма (ПСА).

Зависимость времени работы алгоритма от числа его шагов и представляет собой ВСА. Таким образом, ВСА – это функция, которая каждой входной длине n ставит в соответствие максимальное по всем индивидуальным задачам длины (наихудший случай) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.

абсолютное время работы алгоритма не является объективной оценкой его временной сложности, так как оно зависит от быстродействия реализующей его ЭВМ. Чтобы оценка временной сложности различных алгоритмов была объективной, сравнивают не абсолютное время, а число шагов, за которое алгоритм решает индивидуальную задачу на некоторой абстрактной модели вычислительной машины. В качестве такой универсальной абстрактной модели обычно используется машина Тьюринга или одна из ее разновидностей, а ВСА представляют как оценку функции временной сложности где – некоторая функция, а n – входная длина.

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

Экспоненциальные алгоритмы получили свое название из-за того, что их временная сложность оценивается показательными функциями вида , а частным случаем показательной функции есть экспонента . К экспоненциальным относят и алгоритмы с функциями роста и некоторые другие, скорости роста которых так же велики, как у экспоненты.

18. Понятие о вычислимых, всюду определенных, частичных и частично- рекурсивных функциях. Тезис Черча.

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

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

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

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

С.К. Клини (американский логик и математик) высказал гипотезу о том, что класс алгоритмически вычислимых частичных функций совпадает с классом всех частично рекурсивных функций. Ранее аналогичную гипотезу относительно всюду определенных вычислимых функций выдвинул А Чёрч (американский логик и математик). Гипотезы Чёрча и Клини обычно объединяют в виде тезиса Чёрча.