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

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

$n \log\log n$ находится между и и является относительно распространенным в дикой природе.$n$$n \log n$

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

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

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

Их бесконечно много, так как для любого . Так, в частности, для любого .$O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$$\alpha<\beta$$O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\log n)$$\alpha\in (0,1)$