Classificando funções por crescimento assintótico

35

Suponha que eu tenha uma lista de funções, por exemplo

nloglog(n),2n,n!,n3,nlnn,

Como os classifico assintoticamente, ou seja, após a relação definida por

fOgfO(g) ,

assumindo que eles são realmente comparáveis ​​aos pares (veja também aqui )? Usar a definição de O parece estranho, e muitas vezes é difícil provar a existência de constantes adequadas c e n0 .

Trata-se de medidas de complexidade, por isso estamos interessados ​​no comportamento assintótico como n+ , e assumimos que todas as funções assumem apenas valores não negativos ( n,f(n)0 ).

JAN
fonte
4
Como o OP nunca voltou, estou removendo o material localizado e faço disso uma pergunta de referência.
Raphael

Respostas:

48

Se você deseja uma prova rigorosa, o lema a seguir geralmente é útil. mais útil que as definições.

Se existe, entãoc=limnf(n)g(n)

  • ,c=0 fo(g)
  • ec(0,)fΘ(g)
  • .c=   fω(g)

Com isso, você poderá ordenar a maioria das funções apresentadas na análise de algoritmos¹. Como exercício, prove!

Claro que você deve poder calcular os limites de acordo. Alguns truques úteis para dividir funções complicadas em funções básicas são:

  • Expresse ambas as funções como e compare os expoentes; se a proporção deles tender para 0 ou , o quociente original também.e0
  • De maneira mais geral: se você tiver uma função convexa, continuamente diferenciável e aumentando estritamente para que você possa reescrever seu quociente comoh

    ,f(n)g(n)=h(f(n))h(g(n))

    com egΩ(1)

    ,limnf(n)g(n)=

    então

    .limnf(n)g(n)=

    Veja aqui uma prova rigorosa desta regra (em alemão).

  • Considere continuações de suas funções sobre os reais. Agora você pode usar a regra do L'Hôpital ; esteja atento às suas condições²!

  • Dê uma olhada no equivalente discreto, Stolz – Cesàro .
  • Quando os fatoriais aparecerem, use a fórmula de Stirling :

    n!2πn(ne)n

Também é útil manter um conjunto de relações básicas que você prova uma vez e usa com frequência, como:

  • logaritmos crescem mais lentamente que os polinômios,

    para todos α , β > 0 .(registron)αo(nβ)α,β>0 0

  • ordem dos polinômios:

    para todos osα<β.nαo(nβ)α<β

  • os polinômios crescem mais lentamente que os exponenciais:

    para todosαec>1.nαo(cn)αc>1 1


Pode acontecer que o lema acima não seja aplicável porque o limite não existe (por exemplo, quando as funções oscilam). Nesse caso, considere a seguinte caracterização das classes Landau usando limões superior / inferior :

Com temoscs:=lim supnf(n)g(n)

  • e0cs<fO(g)
  • .cs=0fo(g)

Com temosci:=lim infnf(n)g(n)

  • e0<cifΩ(g)
  • .ci=fω(g)

Além disso,

  • e0<ci,cs<fΘ(g)gΘ(f)
  • .ci=cs=1fg

Verifique aqui e aqui se você está confuso com a minha notação.


Ben Nota bene: Meu colega escreveu uma função do Mathematica que faz isso com êxito em muitas funções, portanto o lema realmente reduz a tarefa à computação mecânica.

² Veja também aqui .

Rafael
fonte
@ Juho Não publicamente, mas é fundamental escrever a si mesmo; calcular Limit[f[n]/g[n], n -> Infinity]e realizar uma distinção entre maiúsculas e minúsculas.
Raphael
20

Outra dica: às vezes, aplicar uma função monótona (como log ou exp) às funções torna as coisas mais claras.

Suresh
fonte
5
Isto deve ser feito com cuidado: , mas 2 2 nS ( 2 N ) . 2nO(n)22nO(2n)
Shaull
2
Destacado. A coisa "aplicar função monótona" parece ser algum tipo de folclore que não funciona em geral. Trabalhamos com critérios suficientes e criamos o que eu publiquei na última revisão da minha resposta .
Raphael
17

Skiena fornece uma lista ordenada das relações de dominância entre as funções mais comuns em seu livro, The Algorithm Design Manual:

n!cnn3n2n1+ϵnlgnnn1/2
lg2nlgnlgnlglgnlglgnα(n)1

Aqui α(n) denota a função inversa de Ackermann .

Robert S. Barnes
fonte
Essa é uma lista estranhamente específica. Muitas das relações (o que significa exatamente) podem ser resumidas em um punhado de lemamas mais gerais.
Raphael
É a notação dele para uma relação de domínio.
Robert S. Barnes
11

Dica: desenhe gráficos dessas funções usando algo como Wolfram Alpha para ter uma ideia de como elas crescem. Observe que isso não é muito preciso, mas se você tentar por números suficientemente grandes, deverá ver os padrões comparativos de crescimento. Obviamente, isso não substitui uma prova.

Por exemplo, tente: log de plotagem (log (n)) de 1 a 10000 para ver um gráfico ou log de plotagem individual (log (n)) e log de plotagem (n) de 1 a 10000 para ver uma comparação.

Dave Clarke
fonte
9
Devemos realmente recomendar o vodoo ?
Raphael
+1 por sugerir desenhar gráficos das funções, embora os gráficos vinculados sejam bastante confusos, a menos que você saiba o que eles significam.
Tsuyoshi Ito
11
Tome um gráfico como uma dica do que você pode querer provar. Essa dica pode estar errada, é claro.
precisa saber é o seguinte
8

Sugiro proceder de acordo com as definições de várias notações. Comece com um par de expressões arbitrário e determine a ordem delas, conforme descrito abaixo. Em seguida, para cada elemento adicional, encontre sua posição na lista classificada usando a pesquisa binária e comparando como abaixo. Então, por exemplo, vamos classificarnregistroregistron e 2n, as duas primeiras funções de n, para iniciar a lista.

Usamos a propriedade que n=2registron reescrever a primeira expressão como nregistroregistron=(2registron)registroregistron=2registronregistroregistron. Poderíamos então usar a definição para mostrar quenregistroregistron=2registronregistroregistrono(2n), já que para qualquer constante c>0 0, há um n0 0 tal que para nn0 0, c(nloglogn)=c(2lognloglogn)<2n.

Next, we try 3n. We compare it to 2n, the largest element we have placed so far. Since 3n=(2log3)n=2nlog3, we similarly show that 2no(3n)=o(2nlog3).

Etc.

Patrick87
fonte
2

Aqui está uma lista da Wikipedia : Quanto menor na tabela, maior a classe de complexidade;

NumameTempo de execuçãoTempo constanteO(1 1)Tempo inverso de AckermannO(uma(n))Tempo logarítmico iteradoO(registron)Log-logarítmicoO(nregistron)Tempo logarítmicoO(registron)Tempo polilogarítmicopoeuy(registron)Poder fracionárioO(nc),Onde 0 0<c<1 1Tempo linearO(n)hora "n log star n"O(nregistron)Tempo quaseilinearO(nregistron)Tempo quadráticoO(n2)Tempo cúbicoO(n3)Tempo polinomialpoeuy(n)=2O(registron)Tempo quase polinomial2O(poeuy(registron))Tempo subexponencial (primeira definição)O(2nϵ),ϵ>0 0Tempo subexponencial (segunda definição)2o(n)Tempo exponencial (com expoente linear)2O(n)Tempo exponencial2poeuy(n)Tempo fatorialO(n!)

Nota : poeuy(x)=xO(1 1)

kelalaka
fonte
1
Also, interesting how the table suggests that 2nlogno(n!). While the table you link to is somewhat accurate, the one linked there (and which you copied) is about complexity classes, which is not a helpful thing to mix in here. Landau notation is not about "time".
Raphael
1
I put this so the name of the complexity classes can be talked directly here. Yes, Landau is more about a specific type of algorithm in Cryptography.
Kelalaka # 19/18
1
I object to some of @Raphael's views. I have been a mathematician and an instructor for many years. I believe, apart from proving those things, a big table like this increases people's intuition easily and greatly. And the names of the asymptotic classes help people remember and communicate a lot.
Apass.Jack
1
@ Apass.Jack Na minha experiência de ensino, quando recebemos uma mesa, muitos alunos a aprendem de cor e deixam de ordenar qualquer função que não esteja na mesa. Observe como esse efeito parece ser responsável por muitas perguntas sobre o crescimento assintótico que ocorrem neste site. Dito isto, é claro que usaremos os lemata implícitos na tabela se isso facilitar as provas, mas isso ocorre depois de aprender como a prova da tabela. (Para enfatizar esse ponto, as pessoas que vêm aqui não precisa de ajuda material de leitura fora de uma mesa eles precisam de ajuda. Provando relações.)
Raphael
11
@kelalaka "Sim, Landau é mais sobre um tipo específico de algoritmo em criptografia." - isso nem faz sentido. A notação Landau é uma abreviação para descrever propriedades de funções matemáticas. Não tem nada a ver com algoritmos e muito menos com criptografia, por si só.
Raphael