Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Пусть имеем 5 алгоритмов различной сложности для решения одной и той же задачи. Положим, что каждое действие алгоритма осуществляется за 1 млс. Характеристики алгоритмов приведены в следующей таблице [27]. Временная Максимальный размер задачи, Алгоритм сложность решаемой за указанное время алгоритма 1 с 1 мин 1 час Al N 1000 60 ОО 3 600 ОО А2 Nlog2N 140 4 893 200 ОО A3 31 244 1 897 А4 N" 10 39 153 А5 9 15 21 Из этой таблицы видно, что увеличение времени решения задачи, напри­ мер с 1-ой секунды до одного часа позволяет для алгоритма^ 7 увеличить раз­ мер решаемой задачи в 3600 раз, а для алгоритма^5 только в 2,33 раза. Предположим, что быстродействие ЭВМ возросло в 10 раз. В нижесле­ дующей таблице показано, как при этом возрастут размеры входов [27]. Из последней таблицы видно, что увеличение быстродействия в 10 раз даёт возможность для алгоритма^ 1 увеличить размер входа в 10 раз, а для алгорит­ ма А5 увеличение размера входа практически не произошло. Таким образом, чем большую временную сложность имеет алгоритм, тем меньшее улучшение даёт увеличение быстродействия. Временная Максимальный размер задачи Алгоритм сложность алгоритма до ускорения после ускорения в 10 раз Al N ^1 10^1 А2 N log2 N S2 10^2 A3 N' S3 3,16^3 А4 N' ^4 2,15 ^4 А5 S5 85+3,3 § 3. Полиномиальные алгоритмы и задачи. Класс F Считается, что алгоритм - полиномиальный или имеет полиномиальную временную сложность, если существует полином р(х) такой, что на любом входном слове длины п алгоритм завершает вычисления после выполнения не более чем р(п) операций. Ясно, что, алгоритмы ^41 и А2, временные сложности которых равны, на- 3/2 2 пример, 0(п ) и 0(п logn), будут считаться полиномиальными, ибо их сложно- 2 3 сти ограничены полиномами, т.е. имеют порядок не выше, чем 0(п ) и 0(п ) со­ ответственно. 221