Existe uma complexidade entre

10

Existe um grau de complexidade maior que e menor que O ( n log n ) ?O(n)O(nlogn)

user3696586
fonte
11
Acho que talvez essa pergunta se encaixe melhor na troca de pilha da Ciência da Computação?
precisa saber é o seguinte
@LKlevin: Concordou.
amigos estão dizendo sobre geoff
2
A troca de pilhas de ciência da computação não é muito amigável para questões básicas como essa.
Nick Alger

Respostas:

20

está entre n e n log n e é relativamente comum de se encontrar na natureza.nloglognnnlogn

Bill Barth
fonte
11
Porém, dependendo da motivação do solicitante, essa pode não ser uma distinção relevante - para todos os fins práticos, é apenas um pequeno fator constante. registroregistron
Eamon Nerbonne
2
Sim, embora isso também seja válido para o , se n for pequeno o suficiente! registronn
Bill Barth
11
@ BillBarth Sim, mas é exponencialmente menos constante que o constante! registroregistron
Pål GD
7

Além de , há também O ( n log ( n ) ) em que log é o número de vezes que a função logaritmo deve ser aplicada para que o resultado seja menor que ou igual a 1.O(nregistro(registro(n)))O(nregistro(n))registro

Por exemplo, se você já conhece uma árvore de abrangência mínima euclidiana, a triangulação de Delaunay pode ser descoberta em O(nregistro(n)) .

Mais extremamente, pode-se observar a função inversa de Ackermann , que pode ser encontrada na análise de vários algoritmos de complexidade O ( n α ( n , n ) ) . Há uma boa introdução aqui .α(n,n)O(nα(n,n))

Peter Brune
fonte
2
Não esqueça a glória que é , a função ackermann inversa iterada! α(n)
Alexis Beingessner
4

Existem infinitas, desde para qualquer α < β . Então, em particular, O ( n ) = O ( n ( log n ) 0 ) O ( n ( log n ) α ) O ( n log n )O(n(registron)α)O(n(registron)β)α<βO(n)=O(n(registron)0 0)O(n(registron)α)O(nregistron)para qualquer .α(0 0,1 1)

David Richerby
fonte