Какова сложность (в стандартном целочисленном ОЗУ) вычисления стандартного дискретного преобразования Фурье вектора из nNn целых чисел? Классический алгоритм для быстрых преобразований Фурье , неуместно [1] приписываемый Кули и Тьюки, обычно описывается как выполняющийся за O(nlogn)О(NжурналN)O(n...
В классической статье Манро и Патерсон изучают проблему того, сколько памяти требуется алгоритму для нахождения медианы в случайно отсортированном массиве. В частности, они ориентированы на следующую модель: ввод читается слева направо в течение числа P раз. Показано, что O ( n12...
Моему 8-летнему надоело создавать обычные лабиринты, и он занялся созданием вариантов, которые выглядят так: Идея состоит в том, чтобы начать с x и достичь o по обычным правилам. Кроме того, вы можете переходить с любого целого числа aaa на любое другое целое число ббb , но вы должны заплатить |...
В 1979 году Фрейвалдс показал, что верификация матричных произведений по любому полю может быть выполнена за рандомизированное время . Более формально, учитывая три матрицы A, B и C, с записями из поля F, проблема проверки, имеет ли AB = C случайный O ( n 2 ) алгоритм...
Я хотел бы вычислить ширину дерева графика. Есть действительно хорошая эвристика для других задач NP-сложных графов, таких как VF2 для изоморфизма подграфа, например, с кодом, доступным в igraph . Я попробовал их на своих графиках и обнаружил, что они работают очень быстро для моих данных....
Очень часто, если время выполнения алгоритма является сложным выражением, сам алгоритм также является сложным и непрактичным. Каждый из корней куба и факторов в асимптотическом времени выполнения имеет тенденцию увеличивать сложность алгоритма, а также скрытые постоянные факторы для времени...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...
Существуют ли алгоритмы решения SAT, не основанные на DPLL? Или все алгоритмы, используемые решателями SAT, основаны на
Похоже, что для некоторых задач NP-Hard много работы по разработке быстрых экспоненциальных алгоритмов с точным временем (т. Е. Результатов вида: Алгоритм A решает задачу за время O (c ^ n), причем c мало). Похоже, что для решения некоторых сложных задач (например, « Измерить и победить»: простой...
Пусть будет классом решений задач, имеющих рандомизированный алгоритм с ограниченной двусторонней ошибкой, работающий за время .O ( f ( n ) )BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n))O(f(n))O(f(n))O(f(n)) ли нам какие-либо проблемы такие, что но ? Доказано ли его несуществование? Q ∈ B P T I M E...
Я никогда раньше не видел алгоритм с логом в знаменателе, и мне интересно, есть ли какие-нибудь действительно полезные алгоритмы с этой формой? Я понимаю много вещей, которые могут привести к умножению логарифмического коэффициента во время выполнения, например, сортировка или алгоритмы на основе...
Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O∗(2n)O∗(2n)O^*(2^n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP? UPD: подавляет полиномиальные факторы.O∗(⋅)O∗(⋅)O^*(\cdot) Самая короткая...
Когда мы рассматриваем алгоритм аппроксимации для задачи минимизации, разрыв интегральности IP-формулировки для этой задачи дает нижнюю границу отношения аппроксимации для определенного класса алгоритмов (таких как алгоритм округления или простой двойственный алгоритм). На самом деле существует...
Предположим , что мы имеем полиномы степени не более n , n > m , так что общее число ненулевых коэффициентов равно n (т. е. многочлены редки). Меня интересует эффективный алгоритм вычисления полинома:p1,...,pmp1,...,pmp_1,...,p_mnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Поскольку...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
У меня много кубоидов в трехмерном пространстве, у каждого есть начальная точка в (x, y, z) и размер (Lx, Ly, Lz). Интересно, как найти самый большой куб в этом трехмерном пространстве, который содержится в объединении кубоидов. Есть ли эффективный алгоритм для этого? Например, если у меня есть...
У меня есть два раздела [1…n][1…n][1 \ldots n] и я ищу расстояние редактирования между ними. Этим я хочу найти минимальное количество отдельных переходов узла в другую группу, которые необходимы для перехода из раздела A в раздел B. Например, расстояние от {0 1} {2 3} {4}в {0} {1} {2 3 4}будет два...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...
Я ищу алгоритм для объединения двух двоичных деревьев поиска произвольного размера и диапазона. Очевидный способ , которым я бы идти о реализации этого было бы найти целые поддерева чьих диапазона может поместиться в произвольный внешний узел в другом дереве. Однако наихудшее время выполнения для...
Задача, которую мы здесь рассматриваем, - это расширение хорошо известной проблемы интервальной раскраски. Вместо интервалов мы рассматриваем прямоугольники, стороны которых параллельны осям. Цель состоит в том, чтобы закрасить прямоугольники минимальным количеством цветов, чтобы любые два...