Aller au contenu

04 · Fonctions usuelles

Intuition

Une poignée de fonctions revient partout : exponentielle, logarithme, puissances, sinus, cosinus. Les connaître, ce n'est pas mémoriser des courbes — c'est savoir par cœur leur domaine, leurs variations, leurs limites, leur dérivée, et les deux ou trois identités qui les caractérisent.

Ce chapitre est un chapitre de mémorisation active. Il n'y a rien à comprendre qui ne soit dit ici ; il y a tout à savoir mobiliser sans réfléchir.

1. Exponentielle

Définition et propriété caractéristique

\(\exp : \mathbb{R}\to\mathbb{R}^{+*}\) est l'unique fonction dérivable vérifiant

\[ \exp' = \exp \qquad\text{et}\qquad \exp(0)=1 \]

On note \(e^x = \exp(x)\), avec \(e = \exp(1)\approx 2{,}71828\).

Propriétés algébriques.

\[ e^{a+b}=e^a e^b \qquad e^{-a}=\frac{1}{e^a} \qquad e^{a-b}=\frac{e^a}{e^b} \qquad (e^a)^n = e^{na} \]

Signe et variations. \(e^x > 0\) pour tout \(x\) — c'est la propriété la plus utilisée : une exponentielle ne s'annule jamais et ne change jamais de signe. \(\exp\) est strictement croissante sur \(\mathbb{R}\).

Limites.

\[ \lim_{x\to-\infty}e^x = 0^+ \qquad \lim_{x\to+\infty}e^x = +\infty \]
\[ \lim_{x\to+\infty}\frac{e^x}{x^n}=+\infty \qquad \lim_{x\to-\infty}x^n e^x = 0 \]

L'inégalité fondamentale

\[ \forall x\in\mathbb{R},\quad e^x \geqslant 1+x \]

avec égalité seulement en \(x=0\). C'est le fait que la courbe est au-dessus de sa tangente en 0 — conséquence de la convexité (\(\exp''=\exp>0\)).

2. Logarithme népérien

Définition

\(\ln : \mathbb{R}^{+*}\to\mathbb{R}\) est la réciproque de \(\exp\) :

\[ y = \ln x \iff x = e^y \qquad (x>0) \]

Sa dérivée est \(\ln'(x) = \dfrac1x\).

Propriétés algébriques.

\[ \ln(ab) = \ln a+\ln b \qquad \ln\frac ab = \ln a - \ln b \qquad \ln(a^n) = n\ln a \qquad \ln\sqrt a = \frac12\ln a \]

Trois interdits

  • \(\ln(a+b) \neq \ln a + \ln b\). Il n'existe aucune formule pour le logarithme d'une somme.
  • \(\ln\) n'est défini que pour des arguments strictement positifs. Écrire \(\ln(x^2) = 2\ln x\) est faux pour \(x<0\) : la bonne écriture est \(\ln(x^2) = 2\ln|x|\).
  • \((\ln x)^2 \neq \ln(x^2)\).

Valeurs et limites. \(\ln1 = 0\), \(\ln e = 1\).

\[ \lim_{x\to0^+}\ln x = -\infty \qquad \lim_{x\to+\infty}\ln x = +\infty \]
\[ \lim_{x\to+\infty}\frac{\ln x}{x^\alpha}=0 \ (\alpha>0) \qquad \lim_{x\to0^+}x^\alpha\ln x = 0 \]

L'inégalité fondamentale

\[ \forall x>0,\quad \ln x \leqslant x-1 \]

C'est la même que celle de l'exponentielle, lue de l'autre côté — voir l'exercice 6 du chapitre 03.

3. Puissances et autres bases

Pour \(a>0\) et \(x\in\mathbb{R}\) :

\[ a^x = e^{x\ln a} \]

C'est la définition à utiliser pour dériver ou étudier ces fonctions.

\[ (a^x)' = \ln a\cdot a^x \qquad (x^\alpha)' = \alpha x^{\alpha-1} \ (x>0) \]

Logarithme en base \(a\) :

\[ \log_a x = \frac{\ln x}{\ln a} \]

En informatique, \(\log_2\) est omniprésent : \(\log_2 x = \frac{\ln x}{\ln 2} \approx 1{,}4427\ln x\).

Dériver \(x^x\)

Ni \(x\cdot x^{x-1}\) ni \(x^x\ln x\). Il faut repasser par l'exponentielle :

\[ x^x = e^{x\ln x} \implies (x^x)' = (\ln x + 1)\,e^{x\ln x} = (\ln x+1)x^x \]

4. Fonctions trigonométriques

4.1 Cercle et valeurs remarquables

\(x\) \(0\) \(\frac\pi6\) \(\frac\pi4\) \(\frac\pi3\) \(\frac\pi2\)
\(\sin x\) \(0\) \(\frac12\) \(\frac{\sqrt2}{2}\) \(\frac{\sqrt3}{2}\) \(1\)
\(\cos x\) \(1\) \(\frac{\sqrt3}{2}\) \(\frac{\sqrt2}{2}\) \(\frac12\) \(0\)
\(\tan x\) \(0\) \(\frac{\sqrt3}{3}\) \(1\) \(\sqrt3\) —

Moyen mnémotechnique

Les sinus sont \(\frac{\sqrt0}{2},\frac{\sqrt1}{2},\frac{\sqrt2}{2}, \frac{\sqrt3}{2},\frac{\sqrt4}{2}\) pour \(0,\frac\pi6,\frac\pi4,\frac\pi3, \frac\pi2\). Les cosinus sont les mêmes dans l'ordre inverse.

4.2 Propriétés

  • \(\sin\) est impaire, \(\cos\) est paire, toutes deux \(2\pi\)-périodiques ;
  • \(\tan = \frac{\sin}{\cos}\) est impaire et \(\pi\)-périodique ;
  • \(\sin^2x+\cos^2x = 1\) pour tout \(x\) ;
  • \(-1\leqslant\sin x\leqslant1\) et de même pour \(\cos\).

Dérivées.

\[ \sin' = \cos \qquad \cos' = -\sin \qquad \tan' = 1+\tan^2 = \frac{1}{\cos^2} \]

Formules d'addition — les seules à connaître, tout le reste en découle :

\[ \cos(a+b) = \cos a\cos b - \sin a\sin b \]
\[ \sin(a+b) = \sin a\cos b+\cos a\sin b \]

Duplication (cas \(b=a\)) :

\[ \sin 2a = 2\sin a\cos a \qquad \cos 2a = \cos^2a-\sin^2a = 2\cos^2a-1 = 1-2\sin^2a \]

Linéarisation

Les deux dernières écritures de \(\cos 2a\) donnent

\[ \cos^2 a = \frac{1+\cos2a}{2} \qquad \sin^2 a = \frac{1-\cos2a}{2} \]

Ces formules sont indispensables pour intégrer \(\cos^2\) et \(\sin^2\) — voir le chapitre 08.

Équations trigonométriques.

\[ \cos x = \cos a \iff x = a+2k\pi \text{ ou } x = -a+2k\pi \]
\[ \sin x = \sin a \iff x = a+2k\pi \text{ ou } x = \pi-a+2k\pi \]

Ne jamais oublier la seconde famille

C'est l'erreur classique : \(\cos x = \frac12\) n'a pas pour seule solution \(x=\frac\pi3\), mais \(x = \pm\frac\pi3 + 2k\pi\).

5. Fonctions hyperboliques

Pas explicitement au programme, mais elles apparaissent dans les calculs d'intégrales et en physique.

\[ \cosh x = \frac{e^x+e^{-x}}{2} \qquad \sinh x = \frac{e^x-e^{-x}}{2} \]
\[ \cosh^2x - \sinh^2x = 1 \qquad \cosh' = \sinh \qquad \sinh' = \cosh \]

Noter le signe moins dans l'identité fondamentale, et l'absence de signe moins dans les dérivées — deux différences avec le cas circulaire.

Exemples traités

Exemple 1 — Équation exponentielle

Résoudre \(e^{2x} - 5e^x + 6 = 0\).

Posons \(X = e^x > 0\). L'équation devient \(X^2-5X+6 = 0\), de racines \(X=2\) et \(X=3\) (somme 5, produit 6).

Les deux sont strictement positives, donc admissibles :

\[ e^x = 2 \implies x = \ln 2 \qquad e^x = 3\implies x = \ln 3 \]

\(\mathcal{S} = \{\ln2\,;\ln3\}\).

Toujours vérifier la positivité

Si l'équation en \(X\) avait donné une racine négative, il aurait fallu l'écarter : \(e^x\) ne peut jamais être négatif.

Exemple 2 — Inéquation logarithmique

Résoudre \(\ln(x-1) + \ln(x+2) \leqslant \ln 4\).

Domaine : \(x-1>0\) et \(x+2>0\), donc \(x>1\).

Sur ce domaine, \(\ln(x-1)+\ln(x+2) = \ln\big((x-1)(x+2)\big)\), et \(\ln\) est strictement croissante :

\[ (x-1)(x+2)\leqslant4 \iff x^2+x-2\leqslant4 \iff x^2+x-6\leqslant0 \]

Racines de \(x^2+x-6\) : \(2\) et \(-3\). Le trinôme est négatif entre elles.

En intersectant avec \(x>1\) :

\[ \mathcal{S} = \left]1\,;2\right] \]

Vérification en \(x=2\) : \(\ln1+\ln4 = \ln4\) ✓ (égalité).

Exemple 3 — Étude d'une fonction avec exponentielle

Étudier \(f(x)=xe^{-x}\) sur \(\mathbb{R}\).

Dérivée : \(f'(x) = e^{-x} - xe^{-x} = (1-x)e^{-x}\).

Comme \(e^{-x}>0\), \(f'\) a le signe de \(1-x\) :

\(x\) \(-\infty\) \(1\) \(+\infty\)
\(f'\) \(+\) 0 \(-\)
\(f\) \(-\infty\) ↗ \(e^{-1}\) ↘ \(0^+\)

Limites. En \(-\infty\) : \(x\to-\infty\) et \(e^{-x}\to+\infty\), donc \(f\to-\infty\). En \(+\infty\) : croissances comparées, \(\frac{x}{e^x}\to0\).

Maximum : \(f(1)=\frac1e\approx0{,}368\).

L'axe des abscisses est asymptote horizontale en \(+\infty\).

Exemple 4 — Équation trigonométrique

Résoudre \(2\cos^2 x - 3\cos x + 1 = 0\) sur \([0;2\pi[\).

Posons \(X=\cos x\in[-1;1]\). Alors \(2X^2-3X+1=0\). Test : \(2-3+1 = 0\), donc \(X=1\) est racine ; l'autre vaut \(\frac{c}{aX_1} = \frac12\).

  • \(\cos x = 1 \implies x = 0\) ;
  • \(\cos x = \frac12 \implies x = \frac\pi3\) ou \(x = -\frac\pi3 \equiv \frac{5\pi}{3}\).
\[ \mathcal{S} = \left\{0,\ \frac\pi3,\ \frac{5\pi}{3}\right\} \]

Erreurs fréquentes

Erreur Correction
\(\ln(a+b)=\ln a+\ln b\) Aucune formule pour la somme
\(\ln(x^2)=2\ln x\) \(= 2\ln\lvert x\rvert\)
\(e^{a}e^{b}=e^{ab}\) \(= e^{a+b}\)
\((x^x)' = x\cdot x^{x-1}\) Passer par \(e^{x\ln x}\)
Oublier une famille de solutions trigonométriques \(\cos x=\cos a\) a deux familles
\(\sqrt{\cos^2 x} = \cos x\) \(= \lvert\cos x\rvert\)

Exercices

★ Exercice 1. Simplifier.

a) \(e^{\ln 5}\) b) \(\ln(e^3)\) c) \(e^{2\ln x}\) pour \(x>0\) d) \(\ln(8)-\ln(2)\)

★ Exercice 2. Résoudre dans \(\mathbb{R}\).

a) \(e^x = 7\) b) \(\ln x = -2\) c) \(e^{3x-1}=1\) d) \(\ln(2x+1)=\ln(x+4)\)

★★ Exercice 3. Dériver.

a) \(f(x)=e^{x^2+1}\) b) \(g(x)=\ln(3x-5)\) c) \(h(x)=x^2\ln x\) d) \(k(x)=\dfrac{e^x}{\ln x}\) e) \(m(x)=2^x\)

★★ Exercice 4. Résoudre.

a) \(e^{2x}-4e^x+3=0\) b) \((\ln x)^2 - 3\ln x + 2 = 0\) c) \(\ln(x)+\ln(x-3) = \ln 4\)

★★ Exercice 5. Résoudre sur \([0;2\pi[\).

a) \(\sin x = \dfrac{\sqrt2}{2}\) b) \(2\sin^2x-\sin x-1=0\) c) \(\cos 2x = \cos x\)

★★★ Exercice 6. Étudier complètement \(f(x)=\dfrac{\ln x}{x}\) sur \(\mathbb{R}^{+*}\) : domaine, dérivée, variations, limites, extremum.

En déduire le nombre de solutions de \(x^a = a^x\) pour \(a>0\) fixé.

★★★ Exercice 7. Soit \(f(x)=\ln\left(\dfrac{1+x}{1-x}\right)\).

a) Déterminer \(D_f\). b) Montrer que \(f\) est impaire. c) Calculer \(f'\) et étudier les variations. d) Montrer que \(f\left(\dfrac{a+b}{1+ab}\right) = f(a)+f(b)\) pour \(a,b\in]-1;1[\).

★★★ Exercice 8. Démontrer, pour tout \(n\in\mathbb{N}^*\) :

\[ \left(1+\frac1n\right)^n < e < \left(1+\frac1n\right)^{n+1} \]

Indication : prenez le logarithme et utilisez l'encadrement \(\frac{1}{n+1} < \ln\left(1+\frac1n\right) < \frac1n\), lui-même issu des inégalités de référence.

★★★★ Exercice 9. Soit \(f(x)=x^{1/x}\) pour \(x>0\).

a) Réécrire \(f\) sous forme exponentielle et déterminer ses variations. b) Montrer que \(f\) admet un maximum et le déterminer. c) En déduire lequel est le plus grand, \(e^\pi\) ou \(\pi^e\) ?

★★★★ Exercice 10 — lien informatique. La complexité d'un algorithme est \(T(n)=n\log_2 n\).

a) Exprimer \(T\) à l'aide du logarithme népérien. b) Un algorithme concurrent est en \(T'(n)=n^{1{,}2}\). Pour quelles valeurs de \(n\) le premier est-il meilleur ? Indication : comparez \(\log_2 n\) et \(n^{0{,}2}\). c) Résoudre numériquement et commenter la taille du seuil. d) Pourquoi la constante cachée dans le \(O\) compte-t-elle davantage que l'exposant dans la plage de tailles réelles ?


Corrigés

Corrigé — Exercice 1

a) \(e^{\ln 5}=5\). b) \(\ln(e^3)=3\). c) \(e^{2\ln x} = \left(e^{\ln x}\right)^2 = x^2\). d) \(\ln 8 - \ln 2 = \ln 4 = 2\ln 2\).

Corrigé — Exercice 2

a) \(x=\ln7\). b) \(x=e^{-2}\). c) \(3x-1 = 0\), donc \(x=\frac13\). d) Domaine : \(2x+1>0\) et \(x+4>0\), soit \(x>-\frac12\). Par injectivité de \(\ln\) : \(2x+1 = x+4\), donc \(x=3\). Compatible ✓

Corrigé — Exercice 3

a) \(f'(x)=2x\,e^{x^2+1}\).

b) \(g'(x)=\dfrac{3}{3x-5}\), pour \(x>\frac53\).

c) \(h'(x)=2x\ln x + x^2\cdot\dfrac1x = 2x\ln x + x = x(2\ln x+1)\).

d) \(k'(x)=\dfrac{e^x\ln x - e^x\cdot\frac1x}{(\ln x)^2} = \dfrac{e^x\left(\ln x - \frac1x\right)}{(\ln x)^2}\).

e) \(m(x)=e^{x\ln2}\), donc \(m'(x)=\ln2\cdot 2^x\).

Corrigé — Exercice 4

a) \(X=e^x\) : \(X^2-4X+3=0\), racines 1 et 3, toutes deux positives.

\[ \mathcal{S}=\{0\,;\ln3\} \]

b) \(X=\ln x\) : \(X^2-3X+2=0\), racines 1 et 2. \(\ln x = 1 \implies x=e\) ; \(\ln x = 2 \implies x=e^2\).

\[ \mathcal{S}=\{e\,;e^2\} \]

c) Domaine : \(x>0\) et \(x-3>0\), donc \(x>3\).

\[ x(x-3)=4 \iff x^2-3x-4=0 \]

Racines \(4\) et \(-1\). Seul \(x=4\) est dans le domaine.

\[ \mathcal{S}=\{4\} \]

Vérification : \(\ln4+\ln1 = \ln4\) ✓

Corrigé — Exercice 5

a) \(\sin x = \sin\frac\pi4\), donc \(x=\frac\pi4\) ou \(x=\pi-\frac\pi4 = \frac{3\pi}{4}\).

\[ \mathcal{S}=\left\{\frac\pi4,\frac{3\pi}4\right\} \]

b) \(X=\sin x\in[-1;1]\) : \(2X^2-X-1=0\). Test \(X=1\) : \(2-1-1=0\) ✓ L'autre racine vaut \(\frac{c}{aX_1}=-\frac12\).

  • \(\sin x=1 \implies x=\frac\pi2\) ;
  • \(\sin x=-\frac12 \implies x = -\frac\pi6\equiv\frac{11\pi}{6}\) ou \(x=\pi+\frac\pi6 = \frac{7\pi}{6}\).
\[ \mathcal{S}=\left\{\frac\pi2,\ \frac{7\pi}6,\ \frac{11\pi}6\right\} \]

c) \(\cos2x = 2\cos^2x-1\). Avec \(X=\cos x\) :

\[ 2X^2-1 = X \iff 2X^2-X-1=0 \]

Mêmes racines qu'en b) : \(X=1\) ou \(X=-\frac12\).

  • \(\cos x=1 \implies x=0\) ;
  • \(\cos x=-\frac12 \implies x=\frac{2\pi}3\) ou \(x=\frac{4\pi}3\).
\[ \mathcal{S}=\left\{0,\ \frac{2\pi}3,\ \frac{4\pi}3\right\} \]
Corrigé — Exercice 6

\(D_f=\mathbb{R}^{+*}\).

\[ f'(x)=\frac{\frac1x\cdot x - \ln x}{x^2} = \frac{1-\ln x}{x^2} \]

Le signe est celui de \(1-\ln x\), positif pour \(x<e\), négatif pour \(x>e\).

\(x\) \(0\) \(e\) \(+\infty\)
\(f'\) \(+\) 0 \(-\)
\(f\) \(-\infty\) ↗ \(\frac1e\) ↘ \(0^+\)

Limites : en \(0^+\), \(\ln x\to-\infty\) et \(\frac1x\to+\infty\), donc \(f\to-\infty\). En \(+\infty\), croissances comparées : \(f\to0^+\).

Maximum : \(f(e)=\dfrac1e\approx0{,}368\).

Application à \(x^a = a^x\). En prenant le logarithme (les deux membres sont positifs pour \(x,a>0\)) :

\[ a\ln x = x\ln a \iff \frac{\ln x}{x} = \frac{\ln a}{a} \iff f(x)=f(a) \]

Il s'agit donc de compter les antécédents de \(f(a)\) par \(f\). D'après le tableau :

Valeur de \(a\) \(f(a)\) Nombre de solutions
\(0<a\leqslant1\) \(\leqslant0\) 1 (branche croissante seulement)
\(1<a<e\) ou \(a>e\) \(\in\left]0;\frac1e\right[\) 2
\(a=e\) \(\frac1e\) (maximum) 1 (\(x=e\))

Exemple célèbre : \(a=2\) donne \(x=2\) et \(x=4\), puisque \(2^4 = 4^2 = 16\).

Corrigé — Exercice 7

a) Il faut \(\dfrac{1+x}{1-x}>0\), soit \(x\in]-1;1[\).

b)

\[ f(-x) = \ln\frac{1-x}{1+x} = \ln\left(\frac{1+x}{1-x}\right)^{-1} = -f(x) \]

Impaire ✓

c) Écrivons \(f(x) = \ln(1+x)-\ln(1-x)\) :

\[ f'(x) = \frac{1}{1+x} + \frac{1}{1-x} = \frac{(1-x)+(1+x)}{1-x^2} = \frac{2}{1-x^2} \]

Sur \(]-1;1[\), \(1-x^2>0\) donc \(f'>0\) : \(f\) est strictement croissante.

Limites : \(f\to-\infty\) en \(-1^+\) et \(f\to+\infty\) en \(1^-\). \(f\) est donc une bijection de \(]-1;1[\) sur \(\mathbb{R}\).

d) Posons \(c = \dfrac{a+b}{1+ab}\). Calculons

\[ 1+c = \frac{1+ab+a+b}{1+ab} = \frac{(1+a)(1+b)}{1+ab} \]
\[ 1-c = \frac{1+ab-a-b}{1+ab} = \frac{(1-a)(1-b)}{1+ab} \]

Donc

\[ \frac{1+c}{1-c} = \frac{(1+a)(1+b)}{(1-a)(1-b)} = \frac{1+a}{1-a}\cdot\frac{1+b}{1-b} \]

En passant au logarithme :

\[ f(c) = f(a)+f(b) \]

\(\blacksquare\)

De quoi s'agit-il

\(f(x) = 2\operatorname{artanh}(x)\), et la formule \(c = \frac{a+b}{1+ab}\) est la loi de composition des vitesses en relativité restreinte (avec \(c=1\)). Elle explique pourquoi additionner deux vitesses inférieures à celle de la lumière donne toujours une vitesse inférieure à celle de la lumière : le domaine \(]-1;1[\) est stable.

Corrigé — Exercice 8

Encadrement préliminaire. Posons \(t = \frac1n > 0\).

De \(\ln(1+t)\leqslant t\) (inégalité de référence), on tire \(\ln\left(1+\frac1n\right) < \frac1n\) (stricte car \(t\neq0\)).

Pour l'autre côté, appliquons \(\ln x\leqslant x-1\) à \(x = \frac{n}{n+1}\) :

\[ \ln\frac{n}{n+1} \leqslant \frac{n}{n+1}-1 = \frac{-1}{n+1} \]

soit, en changeant de signe,

\[ \ln\frac{n+1}{n} \geqslant \frac{1}{n+1} \]

avec inégalité stricte car \(\frac{n}{n+1}\neq1\).

D'où

\[ \frac{1}{n+1} < \ln\left(1+\frac1n\right) < \frac1n \]

Conclusion. Multiplions l'inégalité de droite par \(n>0\) :

\[ n\ln\left(1+\frac1n\right) < 1 \implies \left(1+\frac1n\right)^n < e \]

Multiplions celle de gauche par \(n+1>0\) :

\[ (n+1)\ln\left(1+\frac1n\right) > 1 \implies \left(1+\frac1n\right)^{n+1} > e \]

\(\blacksquare\)

Vérification \(n=10\) : \(1{,}1^{10} = 2{,}5937 < e = 2{,}7183 < 1{,}1^{11} = 2{,}8531\) ✓

Corrigé — Exercice 9

a) \(f(x)=x^{1/x} = e^{\frac{\ln x}{x}} = e^{g(x)}\) avec \(g(x)=\frac{\ln x}{x}\), étudiée à l'exercice 6.

Comme \(\exp\) est strictement croissante, \(f\) a les mêmes variations que \(g\) : croissante sur \(]0;e]\), décroissante sur \([e;+\infty[\).

b) Maximum en \(x=e\) :

\[ f(e) = e^{1/e} \approx 1{,}4447 \]

c) L'inégalité \(f(\pi) < f(e)\) (stricte car \(\pi\neq e\) et \(e\) est le maximum strict) s'écrit

\[ \pi^{1/\pi} < e^{1/e} \]

Élevons à la puissance \(\pi e > 0\) (fonction croissante) :

\[ \pi^{e} < e^{\pi} \]

\(e^\pi\) est le plus grand.

Vérification numérique : \(e^\pi \approx 23{,}141\) et \(\pi^e\approx22{,}459\) ✓

Le résultat général

Pour tout \(x>0\) avec \(x\neq e\) : \(e^x > x^e\). Le nombre \(e\) est « celui qui gagne toujours » quand il est à l'exposant.

Corrigé — Exercice 10

a) \(T(n) = n\log_2 n = \dfrac{n\ln n}{\ln 2} \approx 1{,}4427\,n\ln n\).

b) On compare \(n\log_2 n\) et \(n^{1{,}2}\). En divisant par \(n>0\) :

\[ \log_2 n \quad\text{vs}\quad n^{0{,}2} \]

L'algorithme en \(n\log n\) est meilleur tant que \(\log_2 n < n^{0{,}2}\).

Posons \(h(n) = n^{0{,}2}-\log_2 n\). Les croissances comparées assurent \(h(n)\to+\infty\), donc le \(n\log n\) finit toujours par gagner. Mais le seuil peut être élevé.

c) Résolution numérique.

\(n\) \(\log_2 n\) \(n^{0{,}2}\) Gagnant
\(10\) 3,32 1,58 \(n^{1{,}2}\)
\(10^3\) 9,97 3,98 \(n^{1{,}2}\)
\(10^6\) 19,93 15,85 \(n^{1{,}2}\)
\(10^7\) 23,25 25,12 \(n\log n\)
\(10^9\) 29,90 63,10 \(n\log n\)

Le seuil est entre \(10^6\) et \(10^7\) — plus précisément autour de \(n\approx 3\times10^6\).

Commentaire : sur toute la plage \(n < 10^6\), qui couvre l'immense majorité des usages réels, l'algorithme « asymptotiquement moins bon » en \(n^{1{,}2}\) est en fait plus rapide.

d) Parce que la notation \(O\) efface les constantes, et que dans la plage de tailles réelles ces constantes dominent.

Si l'algorithme en \(n\log_2 n\) a une constante de 100 (beaucoup d'accès mémoire dispersés, allocations, indirections) et celui en \(n^{1{,}2}\) une constante de 1, la comparaison réelle est

\[ 100\,n\log_2 n \quad\text{vs}\quad n^{1{,}2} \]

et le seuil se déplace de plusieurs ordres de grandeur.

C'est exactement ce qu'on a observé pour l'algorithme de Strassen (Algèbre 05, exercice 11) et pour l'algorithme de Stein (Algèbre 11, exercice 11) : l'asymptotique décide de la limite, la constante décide de la pratique.


Chapitre suivant : Étude complète d'une fonction.