Временная сложность

Cтраница 2

Фактически же временная сложность не превышает О ( k ri): цикл while не нужно выполнять более одного раза, потому что, если строка не удаляется при первой итерации, она не будет удалена и при любой последующей итерации, как показывает следующая ниже лемма. [16]

Алгоритм, временная сложность которого не поддается такой оценке, принято называть экспоненциальным. [17]

Найдите функцию временной сложности следующего фрагмента алгоритма, написанного на псевдокоде, подсчитав количество операторов присваивания х: - х 1, которые в нем выполняются. [18]

Алгоритм имеет полиномиальную временную сложность. Вывод и доказательство корректности алгоритма AVOID опускаются ( см. упр. Алгоритм AVOID ( R, В, F) применяется для каждого атрибута В из R. Если выход не пуст, множество выделенных ключей R заменяется на альтернативное множество, полученное алгоритмом AVOID. Известно, что если такое множество ключей существует, то при его использовании атрибут В удалим. Из R - В - В можно вывести новое множество F-зависимостей, представленных в R, так как для R должен существовать новый выделенный ключ К, для которого К - В ( К есть один из замененных ключей, найденных AVOID; см. упр. [19]

Алгоритм имеет полиномиальную временную сложность. Вывод и доказательство корректности алгоритма AVOID опускаются ( см. упр. Алгоритм AVOID ( R, В, F) применяется для каждого атрибута В из R. Если выход не пуст, множество выделенных ключей R заменяется на альтернативное множество, полученное алгоритмом AVOID. Известно, что если такое множество ключей существует, то при его использовании атрибут В удалим. Из R - В - В можно вывести новое множество F-зависимостей, представленных в R, так как для R должен существовать новый выделенный ключ К, для которого К - - В ( К есть один из замененных ключей, найденных AVOID; см. упр. [20]

Далее определим понятие временная сложность. Время, требуемое ДМТ-программой Мдля вычисления при входе X, есть число шагов, выполняемых до момента остановки. [21]

Относительный порядок роста функций. [22]

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

Деревья обязательного предшествования и обязательной преемственности. [24]

Существует алгоритм с временной сложностью О ( ппг), приписывающий всем элементам ( вершинам и дугам) любого сводимого уграфа векторы частот таким образом, что лексико-графическое упорядочение для векторов частот подмножеств элементов уграфа, полученных простым покомпонентным суммированием векторов элементов подмножеств, не противоречит достоверным отношениям частот их выполнения. [25]

Оценка алгоритма с помощью асимптотической временной сложности в худшем случае имеет существенные недостатки. Во-первых, тот худший случай, который определил величину этой оценки, может никогда не встретиться в практике; он может быть весьма искусственным построением. Во-вторых, если скорость роста сложности одного алгоритма меньше скорости роста сложности другого, то это еще не значит, что нужно применять именно первый алгоритм. Поэтому возможно, что при тех размерностях задачи, которые имеются на практике, необходимо использовать второй алгоритм. [26]

Хотя алгоритмы, имеющие временную сложность типа и100 или 10 и2, не могут считаться эффективными с практической точки зрения, естественно возникающие полиномиальные задачи обычно требуют для своего решения ( в самом худшем случае) времени порядка п2 или и3, причем коэффициенты полиномов не слишком велики. [27]

Лемуан и другие занимались временной сложностью евклидовых построений, и тем не менее также поднимался вопрос об объеме пространства, необходимого для этих построений. Хотя использовавшаяся мера пространства ( а именно площадь на плоскости, необходимая для реализации построения) не совпадает с нашим современным определением в смысле количества памяти, занимаемой алгоритмом, она была замечательно близка к нему и весьма естественна. Мы подчеркиваем здесь, что геометрии не чужды представления о времени и памяти. [28]

Заметим, однако, что временная сложность является дважды экспоненциальной относительно размерности пространства. Использование этого метода позволяет эффективно решать некоторые геометрические оптимизационные задачи. [29]

Пусть Т ( п) - временная сложность ( в худшем случае) выполнения п операций ОБЪЕДИНИТЬ и НАЙТИ при условии, что применяется древовидная структура из разд. НАЙТИ, но операция ОБЪЕДИНИТЬ ( Л, В, С) выполняется так: корень дерева А становится сыном корня дерева В независимо от того, какое множество больше. [30]

Страницы: 1 2 3 4