Временная сложность - алгоритм
Cтраница 2
В разделе 7.6 мы занимались исследованием размерности политопа совершенных паросочетаний и получили довольно изящную формулу, представленную в теореме 7.6.6. Сейчас мы будем интересоваться только вопросом о том, полиномиальна ли временная сложность алгоритма вычисления этого числа. [16]
Состыковав расписания для интервалов Jk ( / c l, m), получим расписание s такое, что T ( s) T ( SO. Поскольку оценка временной сложности алгоритма упаковкп равна 0 ( п), то для построения расписания s по заданному расписанию sa требуется выполнить не более 0 ( пг) операций. [17]
В рассматриваемом случае в алгоритме построения оптимальной перестановки на шаге r n - k i ( г - 1, п) в качестве элемента ih достаточно выбрать элемент множества Jh с наибольшим номером. При этом оценка временной сложности алгоритма по-прежнему равна 0 ( пг), но исключается необходимость вычисления значений функций штрафа. В этом случае для построения оптимальной перестановки ( перенумерации требований) необходимо не более O ( nlogn) операций. [18]
 |
Граф G [ IMAGE ] Колесо W7. [19] |
Алгоритм на основе такой эвристики является жадным, так как он раскрашивает граф последовательно вершину за вершиной, присваивая каждой вершине цвет, если это возможно, не учитывая глобальных последствий такой раскраски. Жадный алгоритм задачи раскраски графа очень быстр ( временная сложность алгоритма О ( п)), так как он рассматривает лишь один из возможных вариантов раскраски каждой вершины. [20]
Общее число таких операций, выполняемых в процессе построения, называется его простотой, хотя Лемуан полагал, что, возможно, более уместен термин мера сложности. Это определение близко связано с нашей современной идеей временной сложности алгоритма, хотя в работе Лемуана нет функциональной связи между размером исходной информации ( числом заданных точек и линий) для геометрического построения и его простотой. Безусловно, интерес Лемуана был направлен на улучшение исходных евклидовых построений, а не на развитие теории сложности вычислений. К сожалению, Лемуан не почувствовал важности доказательства, а возможно, просто не смог доказать, что определенное число операций было необходимо для данного построения, и, таким образом, идея о нижней оценке алгоритма ускользнула от него. [21]
В общем случае следует иметь в виду, что повышение скорости работы алгоритма может потребовать увеличения необходимой ему памяти. Этот же пример показывает справедливость обратного утверждения: за счет увеличения временной сложности алгоритма можно понизить его емкостную сложность. [22]
В работе [8] приведен алгоритм построения выпуклой оболочки в трехмерном пространстве без анализа временной сложности алгоритма. [23]
Деревья поиска с указателями довольно сложны для использования в практической реализации алгоритма. Слитор и Тарьян [23] выдвинули гипотезу, что если вместо деревьев поиска с указателями использовать сплей-деревья ( разновидность саморегулирующихся деревьев поиска), то оценка О ( п log log n) для временной сложности алгоритма остается справедливой. Использование сплей-деревьев, возможно, приведет к практически полезной реализации нашего алгоритма, хотя это предположение следует проверить экспериментально. С практической точки зрения в алгоритм следует внести еще некоторые менее значительные изменения. Этот вопрос мы оставим в качестве темы для дальнейших исследований. [24]
Оставшаяся часть данной статьи включает пять разделов и приложение. Эта структура данных состоит из двух уровней деревьев поиска с указателями. Показывается, что с использованием такой структуры данных временная сложность алгоритма вычисления пар видимости, рассматриваемого в разд. В заключение в разд. В приложении приведено описание деревьев поиска с указателями, которые используются не только в алгоритме, непосредственно вычисляющем пары видимости, но и в алгоритме жордановой сортировки. [25]
Основные понятия из теории полиномиальной сводимости дискретных задач и вычислительной сложности алгоритмов вводятся в третьем параграфе. Следует отметить, что, в отличие от первых двух, чтение третьего параграфа требует определенного уровня подготовки. Для чтения остальных глав достаточно такого понятия, как временная сложность алгоритма. [26]
Причем в определенный момент строки с высоким заполнением бывает выгодно хранить в развернутом виде вместе с нулями, а строки с низким заполнением - в компактном. Такая форма хранения помогает уменьшить число необходимых операций и, следовательно, снизить временную сложность алгоритма. [27]
Отметим, что в описанном алгоритме был использован набор методов селекции. Следует отметить, что модифицированные генетические операторы инверсии и ОМ оказывают большое влияние на получение эффективных результатов. Отметим, что отличительной особенностью рассмотренного ГА является способность хорошо работать на популяциях с малым числом хромосом, что уменьшает сложность и временную сложность алгоритма. Подобное улучшение связано с высокой степенью использования миграции популяции в виде регулярных адаптации, выполняемых рассмотренными выше генетическими операторами. Полученные результаты в генетическом решении задачи о коммивояжере позволяют говорить об эффективности метода и целесообразности использования аналогичных подходов в решении других задач оптимизации. [28]
Здесь БС - бинарная строка, показывающая смежность соответствующих вершин в pi и JP2 - То есть, 1 в БС показывает, что вершины 5 и 9 ( рис. 6.48) связаны между собой. Если смежных вершин в заданных родителях нет, тогда бинарная строка заполняется 0 и 1 случайным образом. Остальные переупорядочены так, что элементы остаются в том же порядке, в котором они были в другом родителе. Эта операция имеет временную сложность алгоритма О ( п2), где п - размер хромосомы. [29]
Как видно, наличие вершин с различными локальными степенями упрощает процесс распознавания изоморфизма графов. Это позволяет выбирать начальные условия для эвристики разбиения. В однородных графах все степени вершин одинаковы, поэтому начальные условия выбираются произвольно случайным образом. В этой связи при установлении изоморфизма в однородных графах временная сложность алгоритма в самом лучшем случае равна О ( п), в самом худшем случае - О ( га. Если графы неизоморфны, то за одну итерацию установить результат невозможно. Необходимо провести сравнение на изоморфизм одной случайно выбранной вершины из одного графа со всеми остальными вершинами другого графа. [30]
Страницы: 1 2 3