Алгоритм - сложность
Cтраница 1
Алгоритм сложности 0 ( п1) в9) для умножения целых чисел ( разд. Виноград [1973] рассматривает подобные приемы ускорения с более общей точки зрения. [1]
Алгоритм сложности 0 ( и2) для той же задачи можно найти у Кнута [1971], где содержится также и решение упр. Ху, Таккер [1971] показали, что время О ( я2) и память 0 ( п) достаточны, чтобы построить оптимальное дерево двоичного поиска, в котором данные появляются только на листьях. [2]
Напишите алгоритм сложности Од ( log п), который вычислял бы полином степени п - 1 и все его производные в данной точке. [3]
Найдите алгоритм сложности Оъ ( п Iog2n log log n), который переводил бы ( а) я-разрядные двоичные числа в десятичные; ( б) - разрядные десятичные числа в двоичные. [4]
Известен алгоритм полиномиальной сложности [3], точно решающий эту задачу. [5]
Мы построим алгоритм сложности О ( е log e), вычисляющий доминаторное дерево для корневого ориентированного ациклического графа с е ребрами. Основная наша цель - показать, как комбинировать технику этой главы и предыдущей. Алгоритм основан на трех леммах. [6]
Хорн [295] предложил алгоритм сложности О ( ге2) решения задачи при G ( Л, 0), di О, М 1, ij 0 ( i 1, я) и разрешении прерываний. [7]
В работе приведен алгоритм сложности О ( n2 log / г), строящий такое разбиение поверхности произвольного многогранника, что длина кратчайшего пути из заданной начальной точки 5 ( источника) до произвольной точки t поверхности может быть определена с помощью локализации положения точки t в разбиении. Определение положения точки может быть осуществлено стандартными методами за время О ( log / г), после чего сам путь находится обратной трассировкой за время О ( К), где К - число граней, через которые он проходит. [8]
 |
Самый длинный путь в бесконтурном графе. [9] |
Неизвестно, существует ли алгоритм сложности О ( т) нахождения расстояния от фиксированной вершины до всех остальных вершин графа с неотрицательными весами всех дуг. [10]
Задачи, для решения которых разработаны алгоритмы полиномиальной сложности ( так называемые эффективные алгоритмы), относятся к классу Р - сложных задач. Задачи, которые в настоящее время можно решить только с помощью алгоритмов экспоненциальной сложности, относятся к классу NP-сложных задач. Очевидно, что класс задач Р - сложности является подклассом NP-сложных задач. [11]
 |
Детерминированный конечный автомат, допускающий ( a - - b aabbaab. [12] |
Как только мы заподозрили, что существует алгоритм сложности 0 ( 1 1 lyl) i распознающий, входит ли у в х, его уже нетрудно построить. [13]
Здесь показано время, требуемое машине А для моделирования алгоритма сложности Т ( п) на машине В. При дальнейшем исследовании проблемы можно ожидать, что любая другая разумная модель вычислительной машины будет эквивалентна по сложности перечисленным моделям. [14]
С другой стороны, разбиение задачи на 4 подзадачи размера п / 4 дает алгоритм сложности 0 ( п log п), а на 9 и 16 - порядка log3 и п2 соответственно. Поэтому асимптотически более быстрый алгоритм умножения целых чисел можно было бы получить, если бы удалось так разбить исходные целые числа на 4 части, чтобы суметь выразить исходное умножение через 8 или менее меньших умножений. Другой тип рекуррентных соотношений возникает в случае, когда работа по разбиению задачи не пропорциональна ее размеру. Некоторые типы рекуррентных соотношений вынесены в упражнения. [15]
Страницы: 1 2 3