Математическая логика и теория алгоритмов

Под временной сложностьюзадачи понимается временная сложность наилучшего алгоритма, известного для ее решения. Выясним, как изменяется эффективность различных алгоритмов с ростом быстродействия ЭВМ, на которых реализуются эти алгорит­ мы. Пусть имеем 5 алгоритмов различной сложности для решения одной и той же задачи. Положим, что каждое действие алгоритма осуществляется за 1 млс. Характеристики алгоритмов приведены в табл. 7.1 [29]. Таблица 7. 1 Алгоритм Временная сложность алгоритма Максимальный размер задачи, решаемой за указанное время 1 с 1 мин 1 ч А\ N 1000 60 ОО 36 ОО ОО Л2 A^logjAf 140 4 893 2 ОО ОО A3 31 244 1 897 А4 N' 10 39 153 А5 2" 9 15 21 Из табл. 7.1 видно, что увеличение времени решения задачи, например с одной секунды до одного часа позволяет для алгоритма у11 увеличить размер решаемой задачи в ЗбООО раз, а для алгоритма J5 только в 2,33 раза. Предположим, что быстродействие ЭВМ возросло в 10 раз. В табл. 7.2 показано, как при этом возрастут размеры входов [29]. Таблица 1.2 Алгоритм Временная сложность алгоритма Максимальный размер задачи до ускорения после ускорения в 10 раз Al N SI 10S1 А2 Nlog2N S2 10 S2 A3 S3 3,16 53 А4 S4 2,15 54 А5 2" S5 S5+3.3 280