Qu'est-ce que la notation Big O expliquée: Complexité spatiale et temporelle

Comprenez-vous vraiment Big O? Si c'est le cas, cela rafraîchira votre compréhension avant une entrevue. Sinon, ne vous inquiétez pas - venez nous rejoindre pour des efforts en informatique.

Si vous avez pris des cours liés à l'algorithme, vous avez probablement entendu parler du terme notation Big O . Si ce n'est pas le cas, nous l'examinerons ici, puis nous comprendrons plus en profondeur ce que c'est vraiment.

La notation Big O est l'un des outils les plus fondamentaux pour les informaticiens pour analyser le coût d'un algorithme. C'est également une bonne pratique pour les ingénieurs en logiciel de comprendre en profondeur.

Cet article est écrit en supposant que vous avez déjà abordé du code. En outre, certains documents approfondis nécessitent également des bases en mathématiques au lycée et peuvent donc être un peu moins confortables pour les débutants. Mais si vous êtes prêt, commençons!

Dans cet article, nous aurons une discussion approfondie sur la notation Big O. Nous commencerons par un exemple d'algorithme pour ouvrir notre compréhension. Ensuite, nous aborderons un peu les mathématiques pour avoir une compréhension formelle. Après cela, nous passerons en revue quelques variantes courantes de la notation Big O. À la fin, nous discuterons de certaines des limites de Big O dans un scénario pratique. Une table des matières se trouve ci-dessous.

Table des matières

  1. Qu'est-ce que la notation Big O et pourquoi est-ce important
  2. Définition formelle de la notation Big O
  3. Big O, Little O, Omega et Thêta
  4. Comparaison de complexité entre les Big Os typiques
  5. Complexité temporelle et spatiale
  6. Meilleure, moyenne, pire, complexité attendue
  7. Pourquoi Big O n'a pas d'importance
  8. À la fin…

Alors, commençons.

1. Qu'est-ce que la notation Big O et pourquoi est-ce important

«La notation Big O est une notation mathématique qui décrit le comportement limite d'une fonction lorsque l'argument tend vers une valeur particulière ou l'infini. C'est un membre d'une famille de notations inventées par Paul Bachmann, Edmund Landau et d'autres, collectivement appelées notation Bachmann – Landau ou notation asymptotique. »- Définition de Wikipedia de la notation Big O

En termes simples, la notation Big O décrit la complexité de votre code en utilisant des termes algébriques.

Pour comprendre ce qu'est la notation Big O, nous pouvons jeter un œil à un exemple typique, O (n²) , qui se prononce généralement «Big O au carré» . La lettre «n» représente ici la taille d'entrée , et la fonction «g (n) = n²» à l'intérieur du «O ()» nous donne une idée de la complexité de l'algorithme par rapport à la taille d'entrée.

Un algorithme typique qui a la complexité de O (n²) serait l' algorithme de tri par sélection . Le tri par sélection est un algorithme de tri qui itère dans la liste pour s'assurer que chaque élément à l'index i est le ième élément le plus petit / le plus grand de la liste. Le CODEPEN ci-dessous en donne un exemple visuel.

L'algorithme peut être décrit par le code suivant. Afin de s'assurer que le ième élément est le ième plus petit élément de la liste, cet algorithme effectue d'abord une itération dans la liste avec une boucle for. Ensuite, pour chaque élément, il utilise une autre boucle for pour trouver le plus petit élément dans la partie restante de la liste.

SelectionSort(List) { for(i from 0 to List.Length) { SmallestElement = List[i] for(j from i to List.Length) { if(SmallestElement > List[j]) { SmallestElement = List[j] } } Swap(List[i], SmallestElement) } }

Dans ce scénario, nous considérons la variable List comme l'entrée, donc la taille d'entrée n est le nombre d'éléments à l'intérieur de List . Supposons que l'instruction if et l'affectation de valeur limitée par l'instruction if prennent un temps constant. Ensuite, nous pouvons trouver la grande notation O pour la fonction SelectionSort en analysant combien de fois les instructions sont exécutées.

Tout d'abord, la boucle for interne exécute les instructions à l'intérieur de n fois. Et puis après i est incrémenté, la boucle for interne s'exécute n-1 fois…… jusqu'à ce qu'elle s'exécute une fois, alors les deux boucles for atteignent leurs conditions de fin.

Cela finit en fait par nous donner une somme géométrique, et avec quelques mathématiques du lycée, nous trouverions que la boucle intérieure se répète 1 + 2… + n fois, ce qui équivaut à n (n-1) / 2 fois. Si nous multiplions cela, nous finirons par obtenir n² / 2-n / 2.

Lorsque nous calculons la grande notation O, nous ne nous soucions que des termes dominants et nous ne nous soucions pas des coefficients. Ainsi, nous prenons le n² comme notre grand O final. Nous l'écrivons comme O (n²), qui se prononce à nouveau «Big O au carré» .

Maintenant, vous vous demandez peut-être à quoi sert ce «terme dominant» ? Et pourquoi ne nous soucions-nous pas des coefficients? Ne vous inquiétez pas, nous les passerons en revue un par un. Cela peut être un peu difficile à comprendre au début, mais tout cela aura beaucoup plus de sens en lisant la section suivante.

2. Définition formelle de la notation Big O

Il était une fois un roi indien qui voulait récompenser un homme sage pour son excellence. Le sage n'a demandé que du blé pour remplir un échiquier.

Mais voici ses règles: dans la première tuile, il veut 1 grain de blé, puis 2 sur la deuxième tuile, puis 4 sur la suivante ... chaque tuile de l'échiquier devait être remplie par le double de la quantité de grains que la précédente un. Le roi naïf accepta sans hésitation, pensant que ce serait une demande insignifiante à satisfaire, jusqu'à ce qu'il continue et l'essaye…

Alors, combien de grains de blé le roi doit-il au sage? Nous savons qu'un échiquier a 8 carrés par 8 carrés, ce qui représente 64 tuiles, donc la tuile finale doit avoir 2⁶⁴ grains de blé. Si vous effectuez un calcul en ligne, vous obtiendrez 1,8446744 * 10¹⁹, soit environ 18 suivis de 18 zéros. En supposant que chaque grain de blé pèse 0,01 gramme, cela nous donne 184 467 440 737 tonnes de blé. Et 184 milliards de tonnes, c'est beaucoup, n'est-ce pas?

Les chiffres augmentent assez rapidement plus tard pour une croissance exponentielle, n'est-ce pas? La même logique vaut pour les algorithmes informatiques. Si les efforts requis pour accomplir une tâche augmentent de façon exponentielle par rapport à la taille d'entrée, elle peut finir par devenir extrêmement importante.

Maintenant, le carré de 64 est 4096. Si vous ajoutez ce nombre à 2⁶⁴, il sera perdu en dehors des chiffres significatifs. C'est pourquoi, quand on regarde le taux de croissance, on ne se soucie que des termes dominants. Et puisque nous voulons analyser la croissance par rapport à la taille d'entrée, les coefficients qui ne font que multiplier le nombre plutôt que croître avec la taille d'entrée ne contiennent pas d'informations utiles.

Voici la définition formelle de Big O:

La définition formelle est utile lorsque vous devez effectuer une preuve mathématique. Par exemple, la complexité temporelle pour le tri par sélection peut être définie par la fonction f (n) = n² / 2-n / 2 comme nous l'avons vu dans la section précédente.

Si nous permettons à notre fonction g (n) d'être n², nous pouvons trouver une constante c = 1, et un N₀ = 0, et tant que N> N₀, N² sera toujours supérieur à N² / 2-N / 2. Nous pouvons facilement le prouver en soustrayant N² / 2 des deux fonctions, alors nous pouvons facilement voir que N² / 2> -N / 2 est vrai lorsque N> 0. Par conséquent, nous pouvons arriver à la conclusion que f (n) = O (n²), dans l'autre tri de sélection est «grand O au carré».

You might have noticed a little trick here. That is, if you make g(n) grow supper fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.

Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.

But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.

Question: Une image est représentée par un tableau 2D de pixels. Si vous utilisez une boucle for imbriquée pour parcourir chaque pixel (c'est-à-dire que vous avez une boucle for passant par toutes les colonnes, puis une autre boucle for à l'intérieur pour parcourir toutes les lignes), quelle est la complexité temporelle de l'algorithme lorsque le l'image est considérée comme l'entrée?

3. Big O, Little O, Omega et Thêta

Big O: «f (n) est O (g (n))» ssi pour certaines constantes c et N₀, f (N) ≤ cg (N) pour tout N> N₀Omega: «f (n) est Ω (g ( n)) »ssi pour certaines constantes c et N₀, f (N) ≥ cg (N) pour tout N> N₀Theta:« f (n) est Θ (g (n)) »ssi f (n) est O (g (n)) et f (n) est Ω (g (n)) Little O: «f (n) est o (g (n))» ssi f (n) est O (g (n)) et f ( n) n'est pas Θ (g (n)) - Définition formelle de Big O, Omega, Theta et Little O

En clair:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

Question: Classez les fonctions suivantes du plus complexe au complexe de location. Solution à la question de la section 2: Il s'agissait en fait d'une question piège pour tester votre compréhension. La question essaie de vous faire répondre O (n²) car il y a une boucle for imbriquée. Cependant, n est censé être la taille d'entrée. Puisque le tableau d'images est l'entrée et que chaque pixel n'a été itéré qu'une seule fois, la réponse est en fait O (n). La section suivante passera en revue d'autres exemples comme celui-ci.

5. Complexité temporelle et spatiale

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

Les factorielles peuvent être représentées par des multiplications et peuvent donc être converties en additions en dehors de la fonction logarithmique. Le «n choisir 2» peut être converti en un polynôme avec un terme cubique étant le plus grand.

Et enfin, nous pouvons classer les fonctions de la plus complexe à la moins complexe.

Pourquoi BigO n'a pas d'importance

!!! - ATTENTION - !!! Les contenus discutés ici ne sont généralement pas acceptés par la plupart des programmeurs dans le monde. Discutez-en à vos risques et périls lors d'un entretien. Les gens ont en fait blogué sur la façon dont ils avaient échoué à leurs entretiens avec Google parce qu'ils avaient interrogé l'autorité, comme ici. !!! - ATTENTION - !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!