Есть ли проблемы, у которых самый известный алгоритм имеет время выполнения

Я никогда раньше не видел алгоритм с логом в знаменателе, и мне интересно, есть ли какие-нибудь действительно полезные алгоритмы с этой формой?

Я понимаю много вещей, которые могут привести к умножению логарифмического коэффициента во время выполнения, например, сортировка или алгоритмы на основе дерева, но что может заставить вас делиться на логарифмический коэффициент?

Обычный ответ на вопрос «что может заставить вас делиться на бревно?» это сочетание двух вещей:

1. модель вычислений, в которой допускаются арифметические операции с постоянным временем над целыми числами размера слова, но при этом вы хотите быть осторожными в отношении длины слов, поэтому вы принимаете битов на слово (потому что любое число меньше этого и вы даже не могли бы обратиться ко всей памяти, а также потому, что алгоритмы, использующие поиск таблиц, заняли бы слишком много времени для настройки таблиц, если бы слова были длиннее), и$O(\log n)$
2. алгоритм, который сжимает данные, упаковывая биты в слова, а затем оперирует словами.

Я думаю, что есть много примеров, но классическим примером является Алгоритм четырех русских для самых длинных общих подпоследовательностей и т. Д. Он фактически заканчивается , потому что он использует идею упаковки битов, но затем сохраняет вторую логарифмический фактор, использующий другую идею: замена блоков O ( log 2 n ) битовых операций одним поиском в таблице.$O(n^2/\log^2 n)$$O(\log^2 n)$

Кубик Рубика - очень естественный (и для меня неожиданный) пример. $n\times n\times n$ куба требует $\Theta(n^2/\log n)$ шаги , чтобы решить. (Обратите внимание, что это тета-обозначение, так что это жесткая верхняя и нижняя граница).

Это показано в работе [1].

Возможно, стоит упомянуть, что сложность решения конкретных экземпляров кубика Рубика открыта, но предположительно является NP-трудной (обсуждается здесь, например) NP hard [2]. $\Theta(n^2/\log n)$ алгоритм гарантирует решение, и это гарантирует , что все решения являются асимптотически оптимальными, но она не может решить конкретные случаи оптимально. Ваше определение полезности может применяться или не применяться здесь, поскольку кубики Рубика, как правило, не решаются с помощью этого алгоритма (алгоритм Коциембы обычно используется для маленьких кубов, поскольку он дает быстрые, оптимальные решения на практике).

[1] Эрик Д. Демейн, Мартин Л. Демейн, Сара Эйзенстат, Анна Любив и Эндрю Уинслоу. Алгоритмы решения кубиков Рубика. Материалы 19-го ежегодного Европейского симпозиума по алгоритмам (ESA 2011), 5–9 сентября 2011 г., стр. 689–700

[2] Эрик Д. Демейн, Сара Эйзенстат и Михаил Рудой. Решение кубика Рубика оптимально является NP-полным. Материалы 35-го Международного симпозиума по теоретическим аспектам информатики (STACS 2018), 28 февраля - 3 марта 2018 г., стр. 24: 1-24: 13.

Примером отображаемым в знаменателе без уловок упаковки битов, является недавняя статья Агарвала, Бена Авраама, Каплана и Шарира о вычислении дискретного расстояния Фреше между двумя многоугольными цепями во времени O ( n 2 log log n / log n ) , Хотя я не знаком с деталями алгоритма, один общий трюк состоит в том, чтобы разделить входные данные на относительно небольшие части, а затем умело объединить ответы (конечно, это звучит как «разделяй и властвуй», но вы не получите журнал n в знаменателе с некоторыми хитрыми хитростями)$\log n$$O(n^2\log\log n/\log n)$

Не совсем то, что вы просили, но ситуация «в дикой природе», в которой в знаменателе фигурирует логарифмический фактор, - это статья Стивена Кука, Пьера МакКензи, Дастина Вера, Марка Бравермана, « Галька и программы ветвления для оценки деревьев ». Рахул Сантханам.

Задача оценки дерева (TEP) такова: дано дневное дерево, аннотированное значениями в { 1 , … , k } на листьях и функциях { 1 , … , k } d → { 1 , … , k $d$$\{1,\ldots,k\}$$\{1,\ldots,k\}^d \to \{1,\ldots,k\}$ на внутренних узлах , оцените дерево. Здесь каждый внутренний узел получает значение своей аннотированной функции на значения своих дочерних элементов. Это простая проблема, и цель состоит в том, чтобы показать, что ее невозможно решить в логарифмическом пространстве (когда высота дерева является частью входных данных). В связи с этим нас интересует размер разветвляющихся программ, решающих ТЭП.

В разделе 5 представлены точные границы для деревьев высотой 3, как для TEP, так и для связанной задачи BEP, в которой выходные данные свернуты до каким-то произвольным образом. Для TEP граница равна Θ ( k 2 d - 1 ) , а для BEP граница равна Θ ( k 2 d - 1 / log k ) , т.е. вы получаете сохранение log k .$\{0,1\}$$\Theta(k^{2d-1})$$\Theta(k^{2d-1}/\log k)$$\log k$

Несмотря на то, что речь не идет о времени выполнения, я подумал, что стоит упомянуть классический результат Хопкрофта, Пола и Валианта: [1], поскольку он все еще находится в дух «что может заставить вас сохранить логарифмический фактор».$\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$

Это дает множество примеров проблем, у которых самая известная верхняя граница сложности пространства имеет логин в знаменателе. (В зависимости от вашей точки зрения, я думаю, что либо делает этот пример очень интересным - какая удивительная теорема! - или очень неинтересным - он, вероятно, не «действительно полезен».)

[1] Хопкрофт, Пол и Валиант. По времени против пространства . J. ACM 24 (2): 332-337, 1977.

$\Theta(n/\log n)$

• Проблема взвешивания монет с весами.
• Возглавить с n позиции и 2 цвета.

The best known algorithm for computing the edit (a.k.a. Levenshtein) distance between two strings of length $n$ takes $O((n/\log n)^2)$ time:

William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980).

$\Theta(n/\log n)$ отображается как правильная оценка для проблемы, рассматриваемой Грегом и Полом Валиантом (без связи с хитростями):

Грегори Валиант и Пол Валиант, Мощность линейных оценок, 2011. В 52-м ежегодном симпозиуме IEEE по основам информатики, FOCS 2011.

Вот еще один пример жесткой границы, имеющей логарифмический фактор. (Это теорема 6.17 из Сложности булевых функций: достижения и границы Стасиса Юкны.)

Размер формулы (по полному двоичному базису или базису Де Моргана) проблемы отличимости элементов $\Theta(n^2/\log n)$, где $n$ количество бит на входе

The reason the log factor appears in the denominator is that representing $m$ integers between 1 and $\text{poly}(m)$ requires $n := O(m \log m)$ bits in total, since each integer requires $O(\log m)$ bits. So an upper bound that looks natural in terms of $m$, like $\Theta(m^2 \log m)$, becomes $\Theta(n^2/\log n)$ when expressed in terms of $n$, where $n$ is the number of bits in the input.

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial division of n by each of them takes $\theta(\frac{n}{\log(n)})$ time (assuming division is a constant-time operation)

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.