Raccourcis pour déterminer l’ordre de grandeur

En gardant à l’esprit que \(n\) est la taille des données sur lesquelles un algorithme opère, voici quelques règles générales que vous pouvez utiliser pour déterminer rapidement son ordre de grandeur:

• Si l’algorithme n’accède à aucune donnée, il est en \(O(1)\).
• Si l’algorithme boucle sur les données, il est en \(O(n)\).
• Si l’algorithme comporte deux boucles imbriquées qui itèrent chacune sur les données, il est en \(O(n²)\).
• Les appels de fonction ne comptent pas comme une seule étape, mais plutôt comme le nombre total d’instructions à l’intérieur de la fonction.
• Si l’algorithme comporte une boucle qui divise en deux les données parcourues de manière répétée (diviser pour régner), il est en \(O(log (n))\).
• Si l’algorithme comporte une étape diviser pour régner effectuée une fois par élément dans les données, il est en \(O(n \; log(n))\).
• Si l’algorithme passe par toutes les combinaisons possibles de valeurs dans les données, il est en \(O(k^n)\) (p.ex., \(O(2^n)\) pour toutes les pairs possibles, \(O(3^n)\) pour toutes les triplettes possibles).
• Si l’algorithme passe par toutes les permutations possibles (c’est-à-dire les ordres) des valeurs dans les données, il est en \(O(n!)\).
• Si l’algorithme implique de trier les données, il sera au moins en \(O(n \; log(n))\).