La notation Big O est utile car elle est facile à utiliser et masque les complications et les détails inutiles (pour une certaine définition d'inutile). Une bonne façon de travailler sur la complexité des algorithmes de division pour régner est la méthode de l'arbre. Disons que vous avez une version de tri rapide avec la procédure médiane, donc vous divisez le tableau en sous-tableaux parfaitement équilibrés à chaque fois.

Construisez maintenant un arbre correspondant à tous les tableaux avec lesquels vous travaillez. À la racine, vous avez le tableau d'origine, la racine a deux enfants qui sont les sous-tableaux. Répétez cette opération jusqu'à ce que vous ayez des tableaux d'éléments uniques en bas.

Puisque nous pouvons trouver la médiane en temps O(n) et diviser le tableau en deux parties en temps O(n), le travail effectué à chaque nœud est O(k) où k est la taille du tableau. Chaque niveau de l'arbre contient (au plus) le tableau entier, donc le travail par niveau est O(n) (les tailles des sous-tableaux s'additionnent jusqu'à n, et puisque nous avons O(k) par niveau, nous pouvons l'additionner) . Il n'y a que des niveaux log(n) dans l'arbre depuis chaque fois que nous réduisons de moitié l'entrée.

Nous pouvons donc majorer la quantité de travail par O(n*log(n)).

Cependant, Big O cache certains détails que nous ne pouvons parfois pas ignorer. Envisagez de calculer la suite de Fibonacci avec

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

et supposons simplement que a et b sont des BigIntegers en Java ou quelque chose qui peut gérer des nombres arbitrairement grands. La plupart des gens diraient qu'il s'agit d'un algorithme O(n) sans broncher. Le raisonnement est que vous avez n itérations dans la boucle for et que O(1) fonctionne à côté de la boucle.

Mais les nombres de Fibonacci sont grands, le n-ième nombre de Fibonacci est exponentiel en n donc le simple stockage prendra de l'ordre de n octets. Effectuer une addition avec de grands entiers prendra O(n) quantité de travail. Ainsi, la quantité totale de travail effectuée dans cette procédure est

1 2 3 ... n = n(n-1)/2 = O(n^2)

Cet algorithme s'exécute donc en temps quadradique !

En gros, ce qui revient 90 % du temps, c'est simplement l'analyse des boucles. Avez-vous des boucles imbriquées simples, doubles, triples ? Ensuite, vous avez O(n), O(n^2), O(n^3) temps d'exécution.

Très rarement (sauf si vous écrivez une plate-forme avec une bibliothèque de base étendue (comme par exemple, le .NET BCL ou le STL de C) vous rencontrerez quelque chose de plus difficile que de simplement regarder vos boucles (pour les déclarations , tandis que, aller à, etc...)

Petit rappel : la notation big O est utilisée pour désigner la complexité asymptotique (c'est-à-dire lorsque la taille du problème atteint l'infini), et il cache une constante.