Есть ли сложность между и [закрыто]

10

Существует ли степень сложности, которая больше, чем и меньше, чем ?O(n)O(nlogn)

user3696586
источник
1
Я думаю, что, возможно, этот вопрос лучше подошел бы для обмена компьютерными науками?
Л.Клевин
@LKlevin: Согласен.
Джефф Оксберри
2
Обмен стека информатики не очень дружелюбен к таким базовым вопросам.
Ник Алджер

Ответы:

20

nloglogn находится между и и является относительно распространенным в дикой природе.nnlogn

Билл Барт
источник
1
Хотя, в зависимости от мотивации спрашивающего, это может не иметь отношения к разнице - для всех практических целей - это лишь небольшой постоянный фактор. loglogn
Имон Нербонн
2
Да, хотя это верно и для если достаточно мало! lognn
Билл Барт
1
@BillBarth Да, но она экспоненциально менее постоянна, чем константа ! loglogn
Пол GD
7

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

Например, если вы уже знаете евклидово минимальное остовное дерево, триангуляция Делоне может быть обнаружена за время .O(nlog(n))

Более того, можно взглянуть на обратную функцию Аккермана , которую можно найти при анализе нескольких алгоритмов сложности . Там хорошее введение здесь .α(n,n)O(nα(n,n))

Питер Брюн
источник
2
Не забывайте о славе , итерированной обратной функции ackermann! α(n)
Алексис Бессесснер
4

Их бесконечно много, так как для любого . Так, в частности, для любого .O(n(logn)α)O(n(logn)β)α<βO(n)=O(n(logn)0)O(n(logn)α)O(nlogn)α(0,1)

Дэвид Ричерби
источник