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

Из табл.1 2 видно, что увеличение быстродействия в 10 раз дает возмолшость для алгоритма увеличить размер входа в 10 раз, а для алгоритма А5 увеличение размера входа практически не произошло. Таким образом, чем большую временную сложность имеет алгоритм, тем меньшее улучшение дает увеличение быстродействия. § 3. Полиномиальные алгоритмы и задачи. Класс Р Считается, что алгоритм - полиномиальный или имеет по миачьную временную сложность, если существует полин кой, что на любом входном слове длины п алгоритм завершает вычис­ ления после выполнения не более чем р(п) операций. Ясно, чго алгоритмы А\ и А2, временные сложности которых равны, например, и O( «^log«), будут считаться полиномиальны­ ми, ибо их сложности ограничены полиномами, т.е. имеют порядок не выше, чем 0(«^) и О(и^) соответственно. Говорят, что задача разрешима за полиномиаль полиномиально разрешима, если для нее существует полиномиальный алгоритм. При этом считается, что задача является «хорошей». Множество всех задач, для каждой из которых существует полиномиальный алгоритм, называется классом Р. Среди полиномиальных алгоритмов быстрыми являются линейные алгоритмы, которые обладают сложностью порядка «, где п - размерность входных данных. К линейным алгоритмам относится школьный алгоритм нахождения суммы десятичных чисел, каждое из которых состоит из п цифр, Сложность этого алгоритма - 0(«), В класс Р, кроме линейных задач, попадают, например, сле­ дующие задачи. Умножение целых чисел. Школьный метод умножения двух «-разрядных чисел имеет временную сложность порядка 0(«^). Существует алгоритм Шёнхаге - Штрассена умножения чисел (задан­ ных в двоичной системе счисления) с меньшей сложностью, именно 281