Exemples Java pratiques de la notation Big O

1. Vue d'ensemble

Dans ce didacticiel, nous parlerons de ce que signifie Big O Notation. Nous allons passer par quelques exemples pour étudier son effet sur la durée d'exécution de votre code.

2. L'intuition de la notation Big O

On entend souvent les performances d'un algorithme décrit à l'aide de Big O Notation.

L'étude de la performance des algorithmes - ou complexité algorithmique - relève du domaine de l'analyse des algorithmes. L'analyse des algorithmes répond à la question de savoir combien de ressources, telles que l'espace disque ou le temps, un algorithme consomme.

Nous examinerons le temps comme une ressource. En règle générale, moins un algorithme prend de temps à se terminer, mieux c'est.

3. Algorithmes à temps constant - O (1)

Comment cette taille d'entrée d'un algorithme affecte-t-elle son temps d'exécution? La clé pour comprendre Big O est de comprendre la vitesse à laquelle les choses peuvent croître. Le taux en question ici est le temps pris par taille d'entrée.

Considérez ce simple morceau de code:

int n = 1000; System.out.println("Hey - your input is: " + n);

De toute évidence, peu importe ce que n est ci-dessus. Ce morceau de code prend un temps constant à s'exécuter. Cela ne dépend pas de la taille de n.

De même:

int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);

L'exemple ci-dessus est également un temps constant. Même si son exécution prend 3 fois plus de temps, cela ne dépend pas de la taille de l'entrée, n. Nous désignons les algorithmes à temps constant comme suit: O (1) . Notez que O (2) , O (3) ou même O (1000) signifieraient la même chose.

Nous ne nous soucions pas du temps exact qu'il faut pour fonctionner, mais seulement du temps constant.

4. Algorithmes de temps logarithmique - O (log n)

Les algorithmes à temps constant sont (asymptotiquement) les plus rapides. Le temps logarithmique est le prochain plus rapide. Malheureusement, ils sont un peu plus difficiles à imaginer.

Un exemple courant d'algorithme de temps logarithmique est l'algorithme de recherche binaire. Pour voir comment implémenter la recherche binaire en Java, cliquez ici.

Ce qui est important ici, c'est que le temps d'exécution augmente proportionnellement au logarithme de l'entrée (dans ce cas, connectez-vous à la base 2):

for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }

Si n vaut 8, la sortie sera la suivante:

Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4

Notre algorithme simple a exécuté log (8) = 3 fois.

5. Algorithmes de temps linéaire - O (n)

Après les algorithmes de temps logarithmiques, nous obtenons la classe suivante la plus rapide: les algorithmes de temps linéaire.

Si nous disons que quelque chose se développe linéairement, nous voulons dire qu'il croît directement proportionnellement à la taille de ses entrées.

Pensez à une simple boucle for:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }

Combien de fois cette boucle pour s'exécute-t-elle? n fois, bien sûr! Nous ne savons pas exactement combien de temps cela prendra pour que cela fonctionne - et nous ne nous en soucions pas.

Ce que nous savons, c'est que l'algorithme simple présenté ci-dessus croîtra linéairement avec la taille de son entrée.

Nous préférerions un temps d' exécution de 0,1 n à (1000n + 1000) , mais les deux sont toujours des algorithmes linéaires; ils croissent tous les deux directement proportionnellement à la taille de leurs intrants.

Encore une fois, si l'algorithme a été modifié comme suit:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }

Le runtime serait toujours linéaire dans la taille de son entrée, n . Nous désignons les algorithmes linéaires comme suit: O (n) .

Comme pour les algorithmes à temps constant, nous ne nous soucions pas des spécificités de l'exécution. O (2n + 1) est identique à O (n) , car Big O Notation se préoccupe de la croissance des tailles d'entrée.

6. Algorithmes N Log N Time - O (n log n)

n log n est la classe suivante d'algorithmes. Le temps de fonctionnement augmente proportionnellement à n log n de l'entrée:

for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Par exemple, si le n est 8, alors cet algorithme exécutera 8 * log (8) = 8 * 3 = 24 fois. Que nous ayons une inégalité stricte ou non dans la boucle for n'est pas pertinent pour une notation Big O.

7. Algorithmes de temps polynomiaux - O (np)

Ensuite, nous avons des algorithmes de temps polynomiaux. Ces algorithmes sont encore plus lents que n algorithmes log n .

Le terme polynôme est un terme général qui contient des fonctions quadratiques (n2) , cubiques (n3) , quartiques (n4) , etc. Ce qu'il est important de savoir, c'est que O (n2) est plus rapide que O (n3) qui est plus rapide que O (n4) , etc.

Let's have a look at a simple example of a quadratic time algorithm:

for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

This algorithm will run 82 = 64 times. Note, if we were to nest another for loop, this would become an O(n3) algorithm.

8. Exponential Time Algorithms – O(kn)

Now we are getting into dangerous territory; these algorithms grow in proportion to some factor exponentiated by the input size.

For example, O(2n) algorithms double with every additional input. So, if n = 2, these algorithms will run four times; if n = 3, they will run eight times (kind of like the opposite of logarithmic time algorithms).

O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.

Let's have a look at a simple example of an O(2n) time algorithm:

for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

This algorithm will run 28 = 256 times.

9. Factorial Time Algorithms – O(n!)

In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.

A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.

An explanation of the solution to the traveling salesman problem is beyond the scope of this article.

Instead, let's look at a simple O(n!) algorithm, as in the previous sections:

for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.

Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).

Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).

To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).

Here, the members of our sets are algorithms themselves:

  • Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
  • Enfin, Big Θ décrit l'ensemble de tous les algorithmes qui s'exécutent à une certaine vitesse (c'est comme l'égalité)

Les définitions que nous avons mises ci-dessus ne sont pas mathématiquement exactes, mais elles aideront à notre compréhension.

Habituellement, vous entendrez des choses décrites en utilisant Big O , mais cela ne fait pas de mal de connaître Big Θ et Big Ω.

11. Conclusion

Dans cet article, nous avons discuté de la notation Big O et de la manière dont la compréhension de la complexité d'un algorithme peut affecter la durée d'exécution de votre code.

Une excellente visualisation des différentes classes de complexité peut être trouvée ici.

Comme d'habitude, les extraits de code de ce didacticiel se trouvent à l'adresse over sur GitHub.