Les fonctions sont-elles toujours asymptotiquement comparables?

Lorsque nous comparons la complexité de deux algorithmes, il arrive généralement que $f(n) = O(g(n))$ ou (éventuellement les deux), où et sont les temps d'exécution (par exemple) des deux algorithmes.f $g(n) = O(f(n))$$f$$g$

Est-ce toujours le cas? Autrement dit, au moins une des relations $f(n) = O(g(n))$ et $g(n) = O(f(n))$ toujours valable, c'est-à-dire pour les fonctions générales $f$ , $g$ ? Sinon, quelles hypothèses devons-nous faire et (pourquoi) est-ce correct quand nous parlons des temps d'exécution des algorithmes?

Toutes les paires de fonctions ne sont pas comparables à la notation ; considérons les fonctions f ( n ) = n et g ( n ) = { 1 si  n  est impair , n 2 si  n  est pair . De plus, des fonctions comme g ( n ) apparaissent en fait comme des temps d'exécution d'algorithmes. Considérez l'algorithme de force brute évident pour déterminer si un entier donné n est premier:$O(\cdot)$$f(n) = n$

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

Cet algorithme nécessite opérations arithmétiques lorsque n est pair, O ( $\Theta(1)$$n$ opérations lorsque n est composite, mais Θ ( n ) opérations lorsque n est premier. Ainsi, formellement, cet algorithme estincomparableavec un algorithme qui utilise$O(\sqrt{n})$$n$$\Theta(n)$$n$ opérations arithmétiques pourchaquen.$\sqrt{n}$ $n$

La plupart du temps, lorsque nous analysons des algorithmes, nous voulons uniquement une borne supérieure asymptotique de la forme pour une fonction f relativement simple. Par exemple, la plupart des manuels rapportent simplement (et correctement) lesexécutions dansles opérations arithmétiques O ( n ) . Les fonctions limites supérieures typiques sont des produits d'exponentielles, de polynômes et de logarithmes (bien que des bêtes plus exotiques comme les factorielles et leslogarithmes itérésapparaissent également occasionnellement). Il n'est pas difficile de prouver que deux de ces fonctions sont comparables.$O(f(n))$$f$IsPrime(n)$O(n)$

Voir aussi cette question MathOverflow .

De wikipedia, définition de la grande notation O:

si et seulement s'il y a une constante positive M telle que pour toutes les valeurs suffisamment grandes de , f ( x ) soit au plus M multiplié par g ( x ) en valeur absolue. Autrement dit, f ( x ) ∈ O ( g ( x ) ) si et seulement s'il existe un nombre réel positif $x$$f(x)$$g(x)$$f(x) \in O(g(x))$$M$ et un nombre réel tels que$x_0$

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

Que se passe-t-il pour les fonctions qui ne convergent pas (vers une constante ni l'infini)?

Regardez les fonctions et g ( x ) = $f(x) = |xsin(x)|$$g(x) = 10$

pour chaque , il y a quelques x > x 0 , tels que x = k π , donc f ( x ) = 0 - donc pour chaque M - M $x_0$$x > x0$$x = k\pi$$f(x) = 0$$M$$Mf(x) > g(x)$ donnera faux, et $g(x) \; \not\in O(f(x))$

Cependant, il est facile de voir que n'est pas non plus limité par une constante, donc pour chaque M , x 0 , il y a quelques x > x 0 tels que f ( x ) < M g ( x ) donnera également faux, et $|xsin(x)|$$M$$x_0$$x > x_0$$f(x) < Mg(x)$$f(x) \not\in O(g(x))$

Remarque: pour la définition d'un grand O qui permet une différence constante maximale entre et g ( x ) , la même idée s'appliquera avec g ( x ) = log ( $Mf(x)$$g(x)$$g(x) = \log(x)$

Voici une paire monotone fonctions qui ne sont pas asymptotiquement comparables. Ceci est pertinent car la plupart des complexités qui se posent dans la pratique sont en fait monotones.

$\Gamma$

$\mathcal{L}$$\exp(2\sqrt{\log x + \log\log x})/x^2$$f,g \in \mathcal{L}$$f = o(g)$$f = \omega(g)$$f/g$ tend vers une constante. Voir page 18 de son livre "Ordres de l'infini".

Le résultat est que deux fonctions "simples" se produisant dans l'analyse de l'algorithme sont comparables. Ici, «simple» signifie qu'il n'y a pas de définition par cas (à part un nombre fini de cas de base), et qu'aucune fonction surprenante n'apparaît, comme la fonction Ackermann inverse qui figure parfois dans les temps d'exécution.