Y a-t-il une complexité entre et [fermé]

Existe-t-il un degré de complexité supérieur à et inférieur à ?O ( n log n $O(n)$$O(n \log n)$

situe entre n et n log n , et est relativement commun à trouver dans la nature.$n \log\log n$$n$$n \log n$

En plus de , il y a aussi O ( n log ∗ ( n ) ) dans lequel log ∗ est le nombre de fois où la fonction logarithme doit être appliquée pour que le résultat soit inférieur à ou égal à 1.$O(n\log(\log(n)))$$O(n \log^*(n))$$\log^*$

Par exemple, si vous connaissez déjà un arbre couvrant minimum euclidien, la triangulation de Delaunay peut être découverte en temps .$O(n\log^*(n))$

Plus fort, on peut regarder la fonction inverse d'Ackermann , que l'on retrouve dans l'analyse de plusieurs algorithmes de complexité O ( n α ( n , n ) ) . Il y a une bonne introduction ici .$\alpha(n,n)$$O(n\alpha(n,n))$

Il y en a infiniment, puisque pour tout α < β . Ainsi, en particulier, O ( n ) = O ( n ( log n ) 0 ) ⊊ O ( n ( log n ) α ) ⊊ O ( n log 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)$pour tout .$\alpha\in (0,1)$