Cтраница 4
Разрешается любое изменение полей LLINK и RLINK узлов дерева во время работы алгоритма при условии, что рассматриваемое бинарное дерево имеет стандартное представление [ как в ( 2), например ] как до, так и после прохождения дерева с помощью вашего алгоритма. [46]
Они довольно чувствительны к начальному разбиению, что, в основном, сказывается на времени работы алгоритма. Итерационный эвристический алгоритм начинается со случайного разбиения и затем применяет парный обмен между двумя подмножествами, улучшая начальное решение путем многократной перестановки вершин. [47]
Чтобы проанализировать сложность этого алгоритма, необходимо определить, как быстро уменьшается чисЛо А. Поскольку функция останавливается, если А становится равным 1, скорость, с которой убывает число А, определяет верхнюю границу оценки времени работы алгоритма. Оказывается, что при каждом втором вызове функции Gcd параметр А уменьшается по крайней мере в два раза. [48]
Алгоритм этой статьи был предназначен для достижения наибольшей эффективности на практике. Однако трудно установить строгую верхнюю оценку для времени работы. Время работы алгоритма из [ 1, разд. Они доказали, что для каждого п ее алгоритм заканчивает работу в пределах 0 ( k ( ogn) c log log log) шагов с вероятностью не менее 1 - 2 - для каждого k 1; здесь с - абсолютная эффективно вычислимая постоянная. Можно показать, что та же верхняя оценка верна для подходящей версии нашего алгоритма, ср. Для другой версии верхняя оценка 0 ( ( log n) log log log) может быть строго доказана при допущении справедливости расширенной гипотезы Римана. Мы не входим в детали этого анализа, поскольку существует иной алгоритм, для которого эта верхняя оценка может быть доказана без каких-либо недоказанных допущений. Этот алгоритм, также принадлежащий Адлеману и Румели, описан в [ 1, разд. Однако это не имеет практического значения. [49]
Алгоритм этой статьи был предназначен для достижения наибольшей эффективности на практике. Однако трудно установить строгую верхнюю оценку для времени работы. Время работы алгоритма из [ 1, разд. Они доказали, что для каждого п ее алгоритм заканчивает работу в пределах 0 ( k ( ogn) c log log log) шагов с вероятностью не менее 1 - 2 - для каждого k 1; здесь с - абсолютная эффективно вычислимая постоянная. Можно показать, что та же верхняя оценка верна для подходящей версии нашего алгоритма, ср. Для другой версии верхняя оценка 0 ( ( logn) c log log log) может быть строго доказана при допущении справедливости расширенной гипотезы Римана. Мы не входим в детали этого анализа, поскольку существует иной алгоритм, для которого эта верхняя оценка может быть доказана без каких-либо недоказанных допущений. Этот алгоритм, также принадлежащий Адлеману и Румели, описан в [ 1, разд. Однако это не имеет практического значения. [50]
III, эти процедуры ведут себя намного эффективнее, хотя их логика более трудна для понимания. Время работы алгоритма, получающегося в результате использования указанных процедур, будет зависеть лишь линейно от длины входного списка. [51]
Затем изложим алгоритм, выявляющий в данной цепочке вхождение какой-нибудь цепочки из множества, заданного регулярным выражением. Время работы алгоритма равно по порядку произведению длин цепочки х и данного регулярного выражения. Далее Докажем сильный теоретический результат, состоящий в том, что любую проблему распознавания вхождения цепочек, разрешимую на двустороннем детерминированном магазинном автомате, можно решить на РАМ за линейное время. Это замечательный результат, поскольку магазинный автомат может потребовать для решения задачи квадратичное или даже экспоненциальное время. Наконец, введем понятие дерева позиций ( позиционного дерева) и применим его к другим задачам идентификации цепочек, таким, как поиск в данной цепочке самого длинного повторения. [52]
Программирование этого алгоритма мы оставляем читателю в качестве очень поучительного упражнения ( см. упр. Стоит заметить, что необходимо отвести только одно слово для каждого из узлов BASEROW [ i ], BASECOL [ у ], поскольку большинство их полей несущественно. Время работы алгоритма S приблизительно пропорционально количеству элементов матрицы, которые изменяются при выполнении осевой операции. [53]
В § 5 получены оценки трудоемкости алгоритма Ланцоша для разреженных систем, построенных методом линейного решета. Алгоритм Ланцоша был запрограммирован и апробировался при вычислении индивидуальных значений дискретных логарифмов для модулей логарифмирования размера до 50 десятичных знаков. Замерено время работы алгоритма. [54]
Ниже мы рассмотрим простой алгоритм, который изучает граф и завершается или когда находит цикл, или когда показывает, что циклов в этом графе не существует. Он использует одну структуру данных - список узлов I. Во время работы алгоритма на ребрах графа будет ставиться метка, говорящая о том, что их уже проверили, это делается во избежание повторной проверки. [55]
Ниже мы рассмотрим простой алгоритм, который изучает граф и завершается или когда находит цикл, или когда показывает, что циклов в этом графе не существует. Он использует одну структуру данных - список узлов L. Во время работы алгоритма на ребрах графа будет ставиться метка, говорящая о том, что их уже проверили, это делается во избежание повторной проверки. [56]