Tri des fonctions par croissance asymptotique

Supposons que j'ai une liste de fonctions, par exemple

$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$

Comment puis-je les trier asymptotiquement, c'est-à-dire après la relation définie par

$\qquad f \leq_O g \iff f \in O(g)$ ,

en supposant qu'ils soient effectivement comparables deux à deux (voir aussi ici )? L'utilisation de la définition de $O$ semble délicate et il est souvent difficile de prouver l'existence de constantes appropriées et .$c$$n_0$

Il s’agit de mesures de complexité. Nous nous intéressons donc au comportement asymptotique sous la forme , et supposons que toutes les fonctions prennent uniquement des valeurs non négatives ( ).∀ n , f ( n ) ≥ $n \to +\infty$$\forall n, f(n) \ge 0$

Si vous voulez une preuve rigoureuse, le lemme suivant est souvent utile resp. plus pratique que les définitions.

Si $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ existe, alors

• $c=0 \qquad \ \,\iff f \in o(g)$ ,
• $c \in (0,\infty) \iff f \in \Theta(g)$ et
• $c=\infty \quad \ \ \ \iff f \in \omega(g)$ .

Avec cela, vous devriez pouvoir commander la plupart des fonctions à venir dans l'analyse d'algorithme¹. En exercice, prouvez-le!

Bien entendu, vous devez pouvoir calculer les limites en conséquence. Voici quelques astuces utiles pour décomposer des fonctions complexes en fonctions de base:

• Exprime les deux fonctions en $e^{\dots}$ et compare les exposants; si leur rapport tend vers $0$ ou $\infty$ , le quotient initial en fait de même.

• Plus généralement: si vous avez une fonction convexe, continuellement différentiable et strictement croissante, vous pouvez ainsi ré-écrire votre quotient en tant que$h$

  ,$\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$

  avec et$g^* \in \Omega(1)$

  ,$\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$

  puis

  .$\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

  ^{Voir ici pour une preuve rigoureuse de cette règle (en allemand).}

• Considérez les continuations de vos fonctions sur les réels. Vous pouvez maintenant utiliser la règle de L'Hôpital ; soyez conscient de ses conditions²!

• Regardez l'équivalent discret, Stolz – Cesàro .

• Lorsque les factorielles apparaissent, utilisez la formule de Stirling :

  $\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

Il est également utile de conserver un pool de relations de base que vous avez prouvées une fois et que vous utilisez souvent, telles que:

• les logarithmes croissent plus lentement que les polynômes, c.-à-d.

  pour tout α , β > 0 .$\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$$\alpha, \beta > 0$

• ordre des polynômes:

  pour toutα<β.$\qquad\displaystyle n^\alpha \in o(n^\beta)$$\alpha < \beta$

• les polynômes croissent plus lentement que les exponentielles:

  pour toutαetc>1.$\qquad\displaystyle n^\alpha \in o(c^n)$$\alpha$$c > 1$

---

Il peut arriver qu’au-dessus du lemme ne soit pas applicable car la limite n’existe pas (par exemple, lorsque les fonctions oscillent). Dans ce cas, considérons la caractérisation suivante des classes de Landau en utilisant des limes supérieures / inférieures :

Avec nous avons$c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$

• et$0 \leq c_s < \infty \iff f \in O(g)$
• .$c_s = 0 \iff f \in o(g)$

Avec nous avons$c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$

• et$0 < c_i \leq \infty \iff f \in \Omega(g)$
• .$c_i = \infty \iff f \in \omega(g)$

En outre,

• et$0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$
• $c_i = c_s = 1 \iff f \sim g$.

---

Check here and here if you are confused by my notation.

---

¹ Nota bene: My colleague wrote a Mathematica function that does this successfully for many functions, so the lemma really reduces the task to mechanical computation.

² See also here.

Another tip: sometimes applying a monotone function (like log or exp) to the functions makes things clearer.

Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual:

$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$\gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$

Here $\alpha(n)$ denotes the inverse Ackermann function.

Tip: draw graphs of these functions using something like Wolfram Alpha to get a feeling for how they grow. Note that this is not very precise, but if you try it for sufficiently large numbers, you should see the comparative patterns of growth. This of course is no substitute for a proof.

E.g., try: plot log(log(n)) from 1 to 10000 to see an individual graph or plot log(log(n)) and plot log(n) from 1 to 10000 to see a comparison.

I suggest proceeding according to the definitions of various notations. Start with some arbitrary pair of expressions, and determine the order of those, as outlined below. Then, for each additional element, find its position in the sorted list using binary search and comparing as below. So, for example, let's sort $n^{\log\log n}$ and $2^n$, the first two functions of n, to get the list started.

We use the property that $n = 2^{\log n}$ to rewrite the first expression as $n^{\log\log n} = (2^{\log n})^{\log\log n} = 2^{\log n\log\log n}$. We could then proceed to use the definition to show that $n^{\log\log n} = 2^{\log n\log\log n} \in o(2^n)$, since for any constant $c > 0$, there is an $n_0$ such that for $n \geq n_0$, $c(n^{\log\log n}) = c(2^{\log n\log\log n}) < 2^n$.

Next, we try $3^n$. We compare it to $2^n$, the largest element we have placed so far. Since $3^n = (2^{\log 3})^n = 2^{n\log3}$, we similarly show that $2^n \in o(3^n) = o(2^{n \log 3})$.

Etc.

Here a list from Wikipedia, The lower in the table the bigger complexity class;

$$\begin{array}{|l|l|} \hline Name & \text{Running Time} \\ \hline \text{Constant time} & \mathcal{O}(1) \\ \text{Inverse Ackermann time} & \mathcal{O}(a(n)) \\ \text{Iterated logarithmic time} & \mathcal{O}(\log^*n) \\ \text{Log-logarithmic} & \mathcal{O}(n \log n) \\ \text{Logarithmic time} & \mathcal{O}(\log n) \\ \text{Polylogarithmic time} & poly(\log n) \\ \text{Fractional power} & \mathcal{O}(n^c) ,\text{where } 0<c<1 \\ \text{Linear time} & \mathcal{O}(n) \\ \text{"n log star n" time} & \mathcal{O}(n \log^* n) \\ \text{Quasilinear time} & \mathcal{O}(n \log n) \\ \text{Quadratic time} & \mathcal{O}(n^2) \\ \text{Cubic time} & \mathcal{O}(n^3) \\ \text{Polynomial time} & poly(n) = 2^{\mathcal{O}(\log n)} \\ \text{Quasi-polynomial time} & 2^{\mathcal{O}(poly(\log n))} \\ \text{Sub-exponential time (first definition)} & \mathcal{O}(2^{n^{\epsilon}}), \epsilon >0 \\ \text{Sub-exponential time (second definition)} & 2^{\mathcal{o}(n)}\\ \text{Exponential time(with linear exponent)} & 2^{\mathcal{O}(n)} \\ \text{Exponential time} & 2^{poly(n)} \\ \text{Factorial time} & \mathcal{O}(n!) \\\hline \end{array}$$

note : $poly(x) = x^{\mathcal{O}(1)}$