n * log n e n / log n em relação ao tempo de execução polinomial

12

Eu entendo que Θ(n) é mais rápido que Θ(nlogn) e mais lento que Θ(n/logn) . O que é difícil para mim entender é como realmente comparar Θ(nlogn) e Θ(n/logn) com Θ(nf) onde 0<f<1 .

Por exemplo, como decidimos vs Θ ( n 2 / 3 ) ou Θ ( n 1 / 3 )Θ(n/logn)Θ(n2/3)Θ(n1/3)

Gostaria de ter algumas orientações para prosseguir nesses casos. Obrigado.

mihsathe
fonte

Respostas:

3

Se você apenas desenhar alguns gráficos, estará em boa forma. O Wolfram Alpha é um ótimo recurso para esses tipos de investigações:

equações

Gráfico

Gerado por este link . Observe que, no gráfico, log (x) é o logaritmo natural, razão pela qual a equação de um gráfico parece um pouco engraçada.


fonte
Além de concordar com Raphael, essa imagem daria uma idéia muito melhor , escolher uma faixa ainda maior permite que a segunda função desapareça, o que pode ser confuso.
Phant0m
9

é o inverso de 2 n . Assim como 2 n cresce mais rápido do que qualquer polinômio n klogn2n2nnk independentemente do tamanho de um finito , o log n se tornará mais lento que qualquer função polinomial n k, independentemente de quão pequeno seja um k diferente de zero e positivo .klognnkk

vs n k , para k < 1n/lognnkk<1 é idêntico a: vs n / n 1 - kn/lognn/n1k

como para n grande , n / logn1k>lognn para k < 1 e grande n .n/logn>nkk<1n

Taedrin
fonte
3

Para muitos algoritmos, às vezes acontece que as constantes são diferentes, fazendo com que uma ou outra seja mais rápida ou mais lenta para tamanhos de dados menores e não sejam tão bem ordenadas pela complexidade algorítmica.

Dito isto, se considerarmos apenas os tamanhos de dados super grandes , ou seja. qual deles eventualmente vence, então O(n^f)é mais rápido do que O(n/log n)para 0 < f < 1.

Uma grande parte da complexidade algorítmica é determinar qual algoritmo é eventualmente mais rápido, sabendo que O(n^f)é mais rápido do que O(n/log n)para 0 < f < 1, geralmente é suficiente.

Uma regra geral é que multiplicar (ou dividir) por log neventualmente será insignificante em comparação com multiplicar (ou dividir) por n^fqualquer f > 0.

Para mostrar isso mais claramente, vamos considerar o que acontece à medida que n aumenta.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Observe o que diminui mais rapidamente? É a n^fcoluna.

Mesmo se festivesse mais perto de 1, a n^fcoluna começará apenas mais lentamente, mas à medida que n dobra, a taxa de variação do denominador acelera, enquanto o denominador da n/log ncoluna parece mudar a uma taxa constante.

Vamos traçar um caso particular em um gráfico

enter image description here enter image description here

Fonte: Wolfram Alpha

Eu selecionei O(n^k)tal que ké bastante próximo de 1 (em 0.9). Também selecionei as constantes para que inicialmente O(n^k)sejam mais lentas. No entanto, observe que, eventualmente, "vence" no final e leva menos tempo que O(n/log n).

ronalchn
fonte
que tal n / log n
Isso foi um erro de digitação, foi o que eu quis dizer no começo. De qualquer forma, adicionei um gráfico mais apropriado que mostra que, n^keventualmente, é mais rápido, mesmo que as constantes sejam selecionadas de modo que sejam inicialmente mais lentas.
3

nfnn1fn2/3=n/n1/3

nlognvs.nn1f.

lognnεε>0

A.Schulz
fonte
1

Ao comparar os tempos de execução, é sempre útil compará-los usando grandes valores de n. Para mim, isso ajuda a criar intuição sobre qual função é mais lenta

No seu caso, pense em n = 10 ^ 10 e a = 0,5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Portanto, O (n ^ a) é mais rápido que O (n / logn), quando 0 <a <1 eu usei apenas um valor, no entanto, você pode usar vários valores para criar intuição sobre a função


fonte
1
Não escreva O(10^9), mas o ponto principal sobre a tentativa de alguns números para criar intuição está certo.
Falhou. Isso não está correto. Você substituiu uma única n constante, que pode ser tendenciosa. Se eu escolhesse constantes diferentes, poderia melhorar a aparência de qualquer algoritmo. A notação Big O é usada para estabelecer tendências no que será mais rápido a longo prazo. Para fazer isso, você precisa mostrar que é mais rápido para n grande, mesmo que seja mais lento quando n for menor.
Obrigado. Adicionado vários valores peça e considerar números maiores
Deve-se notar que apenas porque f (a)> g (a) para alguma constante a, não implica necessariamente que O (f (x))> O (g (x)). Isso é útil para criar intuição, mas é insuficiente para compor uma prova rigorosa. Para mostrar que esse relacionamento é válido, você deve mostrar que isso é verdade para TODOS os n grandes, não apenas um n grande. Da mesma forma, você deve mostrar que isso é verdadeiro para todos os polinômios de grau positivo <1
1

Deixei fgdenotar "f cresce assintoticamente mais lento que g", então você pode usar a seguinte regra fácil para polilogarítmica? funções:

nα1(logn)α2(loglogn)α3nβ1(logn)β2(loglogn)β3(α1,α2,α3)<(β1,β2,β3)

The order relation between the tuples is lexicographic. I.e. (2,10)<(3,5) and (2,10)>(2,5)

Applied to your example:

O(n/logn)(1,1,0)

O(n2/3)(2/3,0,0)

O(n1/3)(1/3,0,0)

(1/3,0,0)<(2/3,0,0)<(1,1,0)O(n1/3)O(n2/3)O(n/logn)

You could say: powers of n dominate powers of log, which dominate powers of log log.

Source: Concrete Mathematics, p. 441

phant0m
fonte