As funções são sempre assintoticamente comparáveis?

15

Quando comparamos a complexidade de dois algoritmos, geralmente é o caso que ou (possivelmente ambos), onde e são os tempos de execução (por exemplo) dos dois algoritmos. $f(n) = O(g(n))$ $g(n) = O(f(n))$ $f$ $g$

Esse sempre é o caso? Ou seja, faz pelo menos um dos relacionamentos e segure sempre, que é para funções gerais , ? Caso contrário, quais suposições devemos fazer e (por que) tudo bem quando falamos sobre o tempo de execução do algoritmo? $f(n) = O(g(n))$ $g(n) = O(f(n))$ $f$ $g$

asymptotics mathematical-analysis Rafael
fonte

21

Nem todo par de funções é comparável à notação ; Considere as funções e Além disso, funções como realmente surgem como tempos de execução de algoritmos. Considere o algoritmo óbvio de força bruta para determinar se um número inteiro é primo: $O(\cdot)$ $f(n) = n$

g (n) = {\begin{cases} 1 & if n is odd, \\ n^{2} & if n is even . \end{cases}

$g(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\\ n^2 & \text{if $n$ is even}. \end{cases}$

g (n)

$g(n)$

n

$n$

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

Este algoritmo requer as operações aritméticas quando é par, $\Theta(1)$ $n$ operações quandoé composto, masoperações quandoé primo. Assim, formalmente, esse algoritmo éincomparávelcom um algoritmo que usa $O(\sqrt{n})$ $n$ $\Theta(n)$ $n$ operações aritméticas paracada. $\sqrt{n}$ $n$

Na maioria das vezes, quando analisamos algoritmos, queremos apenas um limite superior assintótico da forma para alguma função relativamente simples . Por exemplo, a maioria dos livros didáticos informaria simplesmente (e corretamente) queé executada em operações aritméticas. Funções típicas de limite superior são produtos de exponenciais, polinômios e logaritmos (embora bestas mais exóticas, como fatoriais elogaritmos iterados,também apareçam ocasionalmente). Não é difícil provar que essas duas funções são comparáveis. $O(f(n))$ $f$ IsPrime(n) $O(n)$

Veja também esta pergunta do MathOverflow .

JeffE
fonte

7

Na wikipedia, definição de grande notação O:

se e somente se houver uma constante positiva M tal que, para todos os valores suficientemente grandes de , seja no máximo M multiplicado por em valor absoluto. Ou seja, se e somente se existir um número real positivo e um número real tal que $x$ $f(x)$ $g(x)$ $f(x) \in O(g(x))$ $M$ $x_0$

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

O que acontece com funções que não convergem (para uma constante nem infinito)?

Veja as funções e $f(x) = |xsin(x)|$ $g(x) = 10$

para cada , existe algum , tal que , portanto, - então, para cada - produzirá falso $x_0$ $x > x0$ $x = k\pi$ $f(x) = 0$ $M$ $Mf(x) > g(x)$ $g(x) \; \not\in O(f(x))$

No entanto, é fácil ver que também não é limitado por nenhuma constante; portanto, para cada , , há alguns modo que também produz falso, e $|xsin(x)|$ $M$ $x_0$ $x > x_0$ $f(x) < Mg(x)$ $f(x) \not\in O(g(x))$

Nota: por definição, se grande ó que permite que a diferença máxima entre constante e , a mesma ideia vai aplicar-se com $Mf(x)$ $g(x)$ $g(x) = \log(x)$

amit
fonte

6

Aqui está um par monotônico estão algumas funções que não são assintoticamente comparáveis. Isso é relevante porque a maioria das complexidades que surgem na prática é de fato monotônica.

f (x) = Γ (⌊ x ⌋ + 1 1) = ⌊ x ⌋!

$f(x) = \Gamma( \lfloor x \rfloor + 1 ) = \lfloor x \rfloor !$

g (x) = Γ (⌊ x - 1 1 / 2 ⌋ + 3 / 2)

$g(x) = \Gamma( \lfloor x-1/2 \rfloor + 3/2 )$

Aqui, é a função gama . A segunda função é especialmente construída para ser muito semelhante ao fatorial, apenas "amostrada" em pontos levemente deslocados na função gama. As funções se cruzam periodicamente de tal maneira que nenhuma delas é assintoticamente ligada pela outra. $\Gamma$

Ambroz Bizjak
fonte

4

$\mathcal{L}$ $\exp(2\sqrt{\log x + \log\log x})/x^2$ . Hardy provou que para cada duas funções $f,g \in \mathcal{L}$ que são positivos e tendem ao infinito, um dos seguintes é verdadeiro: $f = o(g)$ , $f = \omega(g)$ , $f/g$ tende a uma constante. Veja a página 18 de seu livro "Ordens do infinito".

O resultado é que quaisquer duas funções "simples" que ocorrem na análise do algoritmo são comparáveis. Aqui, "simples" significa que não há definição por casos (além de muitos casos-base finitos) e nenhuma função surpreendente aparece, como a função inversa de Ackermann, que às vezes aparece nos tempos de execução.

Yuval Filmus
fonte

Agradável! Vale ressaltar, no entanto, que elementos periódicos ocorrem com freqüência na análise de casos médios (do algoritmo d & c). As que eu conheço são ligadas por ambos os lados por constantes, para que não prejudiquem a comparabilidade assintótica.

Raphael

As funções são sempre assintoticamente comparáveis?

Respostas: