Cтраница 3
Алгоритм называется полиномиальным, если его временная сложность при любом п не превосходит р ( п), где р - некоторый полином, п - входная длина. Алгоритмы, временная сложность которых не допускает такой оценки, называются экспоненциальными. [31]
В данной книге основное внимание уделяется временной сложности, но также указываются и некоторые особые требования к объемам памяти для некоторых алгоритмов. Например, сортировка слиянием ( mergesort), рассматриваемая в главе 9, требует очень больших объемов оперативной памяти. Для других алгоритмов, например пирамидальной сортировки ( heapsort), которая также описывается в главе 9, достаточно обычного объема памяти. [32]
В общем случае процедура прогонки имеет экспоненциальную временную сложность. Если табло Т имеет k столбцов и т строк, chasec ( Т) может иметь т строк ( см. упр. Если использовать процедуру прогонки для проверки отсутствия потерь информации при соединении, то не всегда нужна полная процедура. Как только получена wd, строка из одних выделенных переменных, нет необходимости продолжать проверку. Если wd входит в какое-нибудь табло порождающей последовательности, оно появится в окончательном табло. Для проверки С с существуют другие методы в отличие от метода прогонки, имеющие в случае F - или J-зависимостей полиномиальную временную сложность. [33]
В общем случае процедура прогонки имеет экспоненциальную временную сложность. Если табло Т имеет k столбцов и т строк. Если использовать процедуру прогонки для проверки отсутствия потерь информации при соединении, то не всегда нужна полная процедура. Как только получена wd, строка из одних выделенных переменных, нет необходимости продолжать проверку. Если wd входит в какое-нибудь табло порождающей последовательности, оно появится в окончательном табло. Для проверки С с существуют другие методы в отличие от метода прогонки, имеющие в случае F - или J-зависимостей полиномиальную временную сложность. [34]
Определенную таким образом сложность иногда называют временной сложностью в отличие от сложности по памяти, определяющей величину объема памяти, использованного алгоритмом, как функцию размерности задачи. [35]
Временная сложность в худшем случае ( или просто временная сложность) РАМ-программы - это функция / ( л), равная наибольшей ( по всем входам размера п) из сумм времен, затраченных на каждую сработавшую команду. Временная сложность в среднем - это среднее, взятое по всем входам размера п, тех же самых сумм. [36]
Получим для задачи ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ нижнюю оценку временной сложности в рамках модели алгебраических деревьев решений. [37]
Докажите, что алгоритм 5.4 NONREDUN имеет временную сложность О ( пр), где п - длина входа, р - число F-зависимостей. [38]
В этой статье предлагается алгоритм триангуляции с временной сложностью О ( n log log п) и тем самым показывается, что задача триангуляции и в самом деле более легкая, чем задача сортировки. Все попытки разработать алгоритм с линейной сложностью по-прежнему остаются безуспешными, но предлагаемый нами подход определяет несколько направлений для дальнейшего поиска и проясняет те трудности, которые при этом потребуется преодолеть. [39]
Покажите, что для любой РАМ-программы с временной сложностью Т ( п) при логарифмическом весе существует эквивалентная РАМ-программа с временной сложностью 0 ( Т2 ( п)), в которой нет команд MULT и DIV. Указание: Смоделируйте MULT и DIV подпрограммами, в которых регистры с четными номерами используются для промежуточной памяти. [40]
Посмотрим теперь, как алгоритм 8.8 и его временная сложность влияют на выбор способа выполнения арифметических операций над разреженными полиномами. [41]
Приводится нижняя оценка вида cN log N для временной сложности многоленточной машины Тьюринга, выполняющей умножение в темпе поступления информации / V-разрядных бинарных целых чисел. [42]
Вот еще одно видоизменение этой проблемы: определим временную сложность класса смежности в S как минимальное число шагов, необходимое для того, чтобы вычислить некоторую перестановку в этом классе. Это понятие возникает, если мы интересуемся вычислением автоморфизмов конечной вселенной мощности 2, которая не снабжена специфическим кодированием бинарными словами. Тогда может случиться, что подходящий выбор кодировки может существенно упростить вычисление заданной функции. [43]
Можно показать, что логарифмическая временная сложность алгоритма и временная сложность машины Тьюринга, реализующей этот алгоритм, полиномиально связаны. [44]
Статья Рабина [1963] была одной из первых работ о временной сложности, и она заслуживает изучения. Улучшения иерархии по времени, данные в упр. Что касается иерархий для НМТ, то упр. [45]