Je suis en train d’apprendre les temps d’exécution de la notation Big O et les temps appliqués. Je comprends la notion de temps linéaire O(n), ce qui signifie que la taille de l’entrée affecte proportionnellement la croissance de l’algorithme… et il en va de même, par exemple, pour le temps quadratique O(n2) etc… même pour les algorithmes, tels que les générateurs de permutations, avec des temps O(n !), qui grandissent par factorielle.
Par exemple, la fonction suivante est O(n) parce que l’algorithme augmente proportionnellement à son entrée n :
myfunction(int n) {
for (int i = 0; i < n; ++i)
printf("%d", i);
}
La même chose vaut pour une boucle imbriquée : le temps serait de O(n2).
Mais qu’est-ce que O(log n) exactement ? Par exemple, qu’est-ce que cela signifie de dire que la taille d’un arbre binaire complet est O(log n) ?
Je sais (peut-être pas en détail) ce qu’est le logarithme, en ce sens que : log10(100) = 2, mais je ne comprends pas comment identifier une fonction avec un temps logarithmique.
O(log N) signifie essentiellement que le temps augmente de façon linéaire tandis que n augmente de façon exponentielle. Ainsi, s’il faut 1 seconde pour calculer 10 éléments, il faudra 2 secondes pour calculer 100 éléments, 3 secondes pour calculer 1000 éléments, et ainsi de suite.
Il est O(log n) lorsque nous utilisons des algorithmes de type « diviser pour régner », par exemple la recherche binaire. Un autre exemple est le tri rapide où chaque fois que nous divisons le tableau en deux parties, il faut O(N) pour trouver un élément pivot. Il s’agit donc de N O(log N)
Le dessin suivant représente un arbre binaire. Remarquez que chaque niveau contient le double de nœuds par rapport au niveau supérieur (d’où il vient le nom binaire) :
La recherche binaire est un exemple de complexité O(log n). Supposons que les nœuds du niveau inférieur de l’arbre de la figure 1 représentent des éléments d’une collection triée. La recherche binaire est un algorithme de division et de conquête, et le dessin montre que nous aurons besoin (au maximum) de 4 comparaisons pour trouver l’enregistrement que nous recherchons dans cet ensemble de données de 16 éléments.
Supposons que nous disposions d’un ensemble de données de 32 éléments. Continuez le dessin ci-dessus pour constater que nous aurons besoin de 5 comparaisons pour trouver ce que nous cherchons, car l’arbre n’a gagné qu’un niveau en profondeur lorsque nous avons multiplié la quantité de données. Par conséquent, la complexité de l’algorithme peut être décrite comme un ordre logarithmique.
En traçant log(n) sur une feuille de papier ordinaire, on obtient un graphique où la montée de la courbe se ralentit au fur et à mesure que n augmente :
1 milliseconde si vous avez 2 éléments.
2 millisecondes si vous avez 4 éléments.
3 millisecondes si vous avez 8 éléments.
4 millisecondes si vous avez 16 éléments.
…
n millisecondes si vous avez 2^n éléments.
Cela prend donc log2(n) temps. La notation Big O, signifie que la relation n’a besoin d’être vraie que pour les grand n, et que les facteurs constants et les termes plus petits peuvent être ignorés.
Le temps d’exécution logarithmique (O(log n)) signifie essentiellement que le temps d’exécution croît proportionnellement au logarithme de la taille de l’entrée. Exemple, si 10 éléments prennent au plus un certain temps x, et 100 éléments prennent au plus, disons, 2x, et que 10 000 éléments prennent au maximum 4x, alors il s’agit d’une complexité temporelle de O(log n).
