Линейное время

Cтраница 2

Далее мы увидим, что все задачи о близости точек можно свести за линейное время к задаче ДИАГРАММА ВОРОНОГО, и, следовательно, существует много различных способов доказательства этой теоремы. [16]

Алгоритм 9.5 можно модифицировать так, чтобы он строил уплотненные позиционное и вспомогательное деревья за линейное время. Мы не приводим здесь этот модифицированный алгоритм потому, что он аналогичен алгоритму 9.5, а также потому, что во многих приложениях можно ожидать, что размер позиционного дерева будет пропорционален длине входной цепочки. В замечаниях по литературе указаны работы, в которых излагается алгоритм с уплотнением позиционного дерева и другие его приложения. [17]

Время выполнения МОДПЙЕЮШ pciiitKMH нелинейно, [ [ осьольку лля KHT3 jai i КС-кивки чожст трсбонатьси линейное время. [18]

Если исходные данные уже упорядочены, то, используя метод Грэхема, можно найти нижнюю оболочку за линейное время. [19]

Если уже найдены пересечения верхних полуплоскостей и нижних полуплоскостей, то пересечение двух неограниченных многоугольников может быть найдено за линейное время, например, методом заметания плоскости, так как ребра, определяющие пересечения, упорядочены. Таким образом, имеет место следующая теорема. [20]

Нетрудно показать, что задача о 2-выполнимости относится к классу Р; в действительности ее можно решить детерминированным алгоритмом за линейное время. Однако оказывается, что ситуация меняется при / г З, поскольку мы можем доказать следующее. [21]

Построение выпуклой оболочки по диаграмме Вороного. [22]

Теорема 5.19. Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время. [23]

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

При снижении потерь линейного времени относительно норматива каждый час должен добавлять в Фбр определенную сумму Ф % 1 в, зависящую от абсолютной величины сложившихся потерь линейного времени по данному агрегату, системе и от ее удельного веса в общих потерях линейного времени. [25]

Если глубина каждого направленного ациклического графа с п ребрами может быть приведена к log n удалением только о ( п) ребер, то недетерминированные многоленточные машины Тьюринга за линейное время могут распознавать языки, не распознаваемые детерминированными многоленточными машинами Тьюринга за такое же время. Для некоторых графов уменьшение глубины до log п требует удаления Q ( / z / log log п) ребер. Дается теоретико-графовое условие того, что забывчивость ( obliviousness) уменьшает мощность многоленточных машин Тьюринга. [26]

Алгоритмы построения выпуклой оболочки, основанные на методе разделяй и властвуй, разбивающие исходное множество точек на две части, строящие выпуклую оболочку для каждой из этих частей и затем объединяющие их за линейное время, являются геометрическими аналогами алгоритма сортировки слиянием. Алгоритм, строящий выпуклую оболочку в реальном времени, является аналогом алгоритма сортировки вставками. Аналоги алгоритма быстрой сортировки обсуждались в разд. [27]

Связь задач о близости с основными задачами, используемыми в качестве вычислительных прототипов. [28]

В предыдущем разделе уже говорилось о том, что ЕМОД содержит кратчайшее ребро евклидова графа на множестве из N точек, и, следовательно, задача БЛИЖАЙШАЯ ПАРА тривиальным образом сводится к ЕМОД за линейное время. [29]

В предыдущем разделе мы показали, что если задачу идентификации образов можно сформулировать как задачу распознавания языка, для которой можно найти решающий ее 2ДМА, то исходную задачу идентификации образов можно решить за линейное время. Можно было бы взять прямо алгоритм 9.4 как алгоритм линейной сложности, решающий исходную задачу. Но мультипликативная постоянная, возникающая при таком моделировании, сделала бы этот подход в лучшем случае непривлекательным. [30]

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