Qu'est-ce que O (…) et comment le calculer?

Aidez-moi! J'ai une question où j'ai besoin d'analyser le Big-O d'un algorithme ou d'un code.

• Je ne sais pas exactement ce qu'est Big-O ou comment il se rapporte à Big-Theta ou à d'autres moyens d'analyser la complexité d'un algorithme.

• Je ne sais pas si Big-O fait référence au temps d'exécution du code ou à la quantité de mémoire nécessaire (compromis espace / temps).

• J'ai des devoirs en informatique où j'ai besoin de faire quelques boucles, peut-être un algorithme récursif, et de trouver le Big-O pour cela.

• Je travaille sur un programme où j'ai le choix entre deux structures de données ou algorithmes avec un Big-O connu, et je ne sais pas lequel choisir.

Comment puis-je comprendre comment calculer et appliquer Big-O à mon programme, mes devoirs ou mes connaissances générales en informatique?

Remarque: cette question est une cible canonique dupe pour d'autres questions Big-O tel que déterminé par la communauté . Il est intentionnellement large de pouvoir contenir une grande quantité d'informations utiles pour de nombreuses questions Big-O. Veuillez ne pas utiliser le fait qu'il soit aussi large comme indication que des questions similaires sont acceptables.

Le O (...) fait référence à la notation Big-O, qui est un moyen simple de décrire le nombre d'opérations qu'un algorithme prend pour faire quelque chose. C'est ce qu'on appelle la complexité temporelle .

En notation Big-O, le coût d'un algorithme est représenté par son opération la plus coûteuse en grand nombre. Si un algorithme prenait des mesures, il serait représenté O (n ³ ). Un algorithme qui compterait chaque élément d'une liste fonctionnerait en temps O (n), appelé temps linéaire.n3 + n2 + n

Pour une liste des noms et des exemples classiques sur Wikipédia: Ordres des fonctions communes

Matériel connexe:

• Explication en anglais simple de Big O (SO)
• Existe-t-il un système derrière la magie de l'analyse algorithmique? (CS.SE)
• Guide du débutant sur la notation Big O
• Algorithmes: conception et analyse

Quelles sont les fonctions asymptotiques? Qu'est-ce qu'une asymptote, de toute façon?

Étant donné une fonction f (n) qui décrit la quantité de ressources (temps CPU, RAM, espace disque, etc.) consommées par un algorithme lorsqu'il est appliqué à une entrée de taille n , nous définissons jusqu'à trois notations asymptotiques pour décrire ses performances pour grand n .

Une asymptote (ou fonction asymptotique) est simplement une autre fonction (ou relation) g (n) à laquelle f (n) se rapproche de plus en plus lorsque n grandit de plus en plus, mais n'atteint jamais tout à fait. L'avantage de parler de fonctions asymptotiques est qu'elles sont généralement beaucoup plus simples à aborder même si l'expression de f (n) est extrêmement compliquée. Les fonctions asymptotiques sont utilisées dans le cadre des notations de délimitation qui restreignent f (n) au-dessus ou au-dessous.

(Remarque: dans le sens utilisé ici, les fonctions asymptotiques ne sont proches de la fonction d'origine qu'après correction d'un facteur non nul constant, car les trois notations big-O / Θ / Ω ne tiennent pas compte de ces facteurs constants de leur considération.)

Quelles sont les trois notations limites asymptotiques et en quoi sont-elles différentes?

Les trois notations sont utilisées comme ceci:

f (n) = O (g (n))

où f (n) est ici la fonction d'intérêt, et g (n) est une autre fonction asymptotique avec laquelle vous essayez d'approximer f (n) . Cela ne doit pas être considéré comme une égalité au sens strict, mais comme une déclaration formelle entre la vitesse à laquelle f (n) croît par rapport à n par rapport à g (n) , lorsque n devient grand. Les puristes utiliseront souvent la notation alternative f (n) ∈ O (g (n)) pour souligner que le symbole O (g (n)) est en réalité toute une famille de fonctions qui partagent un taux de croissance commun.

La notation Big-ϴ (Theta) indique une égalité sur la croissance de f (n) jusqu'à un facteur constant (plus de détails plus loin). Il se comporte comme un =opérateur pour les taux de croissance.

La notation Big-O décrit une limite supérieure de la croissance de f (n) . Il se comporte comme un ≤opérateur pour les taux de croissance.

La notation Big-Ω (Omega) décrit une limite inférieure sur une croissance de f (n) . Il se comporte comme un ≥opérateur pour les taux de croissance.

Il existe de nombreuses autres notations asymptotiques , mais elles ne se produisent pas aussi souvent dans la littérature informatique.

Les notations Big-O et leurs semblables sont souvent un moyen de comparer la complexité temporelle .

Qu'est-ce que la complexité temporelle?

La complexité temporelle est un terme de fantaisie pour la durée T (n) nécessaire à un algorithme pour s'exécuter en fonction de sa taille d'entrée n . Cela peut être mesuré en quantité de temps réel (par exemple secondes), en nombre d'instructions CPU, etc. On suppose généralement que l'algorithme s'exécutera sur votre ordinateur d' architecture von Neumann de tous les jours . Mais bien sûr, vous pouvez utiliser la complexité du temps pour parler de systèmes informatiques plus exotiques, où les choses peuvent être différentes!

Il est également courant de parler de la complexité de l'espace en utilisant la notation Big-O. La complexité de l'espace est la quantité de mémoire (stockage) requise pour terminer l'algorithme, qui peut être de la RAM, un disque, etc.

Il peut arriver qu'un algorithme soit plus lent mais utilise moins de mémoire, tandis qu'un autre est plus rapide mais utilise plus de mémoire. Chacun peut être plus approprié dans des circonstances différentes, si les ressources sont limitées différemment. Par exemple, un processeur intégré peut avoir une mémoire limitée et favoriser l'algorithme plus lent, tandis qu'un serveur dans un centre de données peut avoir une grande quantité de mémoire et favoriser l'algorithme plus rapide.

Calcul de Big-ϴ

Le calcul du Big-ϴ d'un algorithme est un sujet qui peut remplir un petit manuel ou environ un demi-semestre de cours de premier cycle: cette section couvrira les bases.

Étant donné une fonction f (n) dans le pseudocode:

int f(n) {
  int x = 0;
  for (int i = 1 to n) {
    for (int j = 1 to n) {
      ++x;
    }
  }
  return x;
}

Quelle est la complexité temporelle?

La boucle externe s'exécute n fois. Pour chaque fois que la boucle externe s'exécute, la boucle interne s'exécute n fois. Cela met le temps de fonctionnement à T (n) = n ² .

Considérons une deuxième fonction:

int g(n) {
  int x = 0;
  for (int k = 1 to 2) {
    for (int i = 1 to n) {
      for (int j = 1 to n) {
        ++x;
      }
    }
  }
  return x;
}

La boucle extérieure s'exécute deux fois. La boucle du milieu s'exécute n fois. Pour chaque fois que la boucle du milieu s'exécute, la boucle intérieure s'exécute n fois. Cela met le temps de course à T (n) = 2n ² .

Maintenant, la question est, quel est le temps de fonctionnement asymptotique des deux fonctions?

Pour calculer cela, nous effectuons deux étapes:

• Supprimez les constantes. À mesure que les algorithmes augmentent dans le temps en raison des entrées, les autres termes dominent le temps d'exécution, ce qui les rend sans importance.
• Supprimer tout sauf le terme le plus grand. Lorsque n va à l'infini, n ² dépasse rapidement n .

La clé ici est de se concentrer sur les termes dominants et de simplifier ces termes .

T (n) = n ² ∈ ϴ (n ² )
T (n) = 2n ² ∈ ϴ (n ² )

Si nous avons un autre algorithme avec plusieurs termes, nous le simplifierions en utilisant les mêmes règles:

T (n) = 2n ² + 4n + 7 ∈ ϴ (n ² )

La clé de tous ces algorithmes est que nous nous concentrons sur les termes les plus gros et supprimons les constantes . Nous ne regardons pas le temps de fonctionnement réel, mais la complexité relative .

Calcul de Big-Ω et Big-O

Tout d'abord, sachez que dans la littérature informelle , «Big-O» est souvent traité comme synonyme de Big-Θ, peut-être parce que les lettres grecques sont difficiles à taper. Donc, si quelqu'un à l'improviste vous demande le Big-O d'un algorithme, il veut probablement son Big-Θ.

Maintenant, si vous voulez vraiment calculer Big-Ω et Big-O dans les sens formels définis précédemment, vous avez un problème majeur: il existe une infinité de descriptions Big-Ω et Big-O pour une fonction donnée! C'est comme demander quels sont les nombres inférieurs ou égaux à 42. Il existe de nombreuses possibilités.

Pour un algorithme avec T (n) ∈ ϴ (n ² ) , l'une des déclarations suivantes est formellement valide à faire:

• T (n) ∈ O (n ² )
• T (n) ∈ O (n ³ )
• T (n) ∈ O (n ⁵ )
• T (n) ∈ O (n ¹²³⁴⁵ × e ⁿ )
• T (n) ∈ Ω (n ² )
• T (n) ∈ Ω (n)
• T (n) ∈ Ω (log (n))
• T (n) ∈ Ω (log (log (n)))
• T (n) ∈ Ω (1)

Mais il est incorrect d'énoncer T (n) ∈ O (n) ou T (n) ∈ Ω (n ³ ) .

Qu'est-ce que la relative complexité? Quelles classes d'algorithmes existe-t-il?

Si nous comparons deux algorithmes différents, leur complexité lorsque l'entrée va à l'infini augmentera normalement. Si nous examinons différents types d'algorithmes, ils peuvent rester relativement les mêmes (disons différer par un facteur constant) ou peuvent diverger considérablement. C'est la raison d'effectuer l'analyse Big-O: pour déterminer si un algorithme fonctionnera raisonnablement avec de grandes entrées.

Les classes d'algorithmes se décomposent comme suit:

• Θ (1) - constant. Par exemple, choisir le premier numéro d'une liste prendra toujours le même temps.

• Θ (n) - linéaire. Par exemple, itérer une liste prendra toujours un temps proportionnel à la taille de la liste, n .

• Θ (log (n)) - logarithmique (la base n'a généralement pas d'importance). Les algorithmes qui divisent l'espace d'entrée à chaque étape, comme la recherche binaire, en sont des exemples.

• Θ (n × log (n)) - temps linéaire logarithmique («linéithmique»). Ces algorithmes divisent et conquièrent généralement ( log (n) ) tout en itérant ( n ) toutes les entrées. De nombreux algorithmes de tri populaires (tri par fusion, Timsort) entrent dans cette catégorie.

• Θ (n ^m ) - polynôme ( n élevé à toute constante m ). Il s'agit d'une classe de complexité très courante, souvent trouvée dans les boucles imbriquées.

• Θ (m ⁿ ) - exponentielle (toute constante m élevée à n ). De nombreux algorithmes récursifs et graphiques entrent dans cette catégorie.

• Θ (n!) - factoriel. Certains graphes et algorithmes combinatoires sont de complexité factorielle.

Cela a-t-il quelque chose à voir avec le meilleur / moyen / pire cas?

Non. Big-O et sa famille de notations parlent d'une fonction mathématique spécifique . Ce sont des outils mathématiques utilisés pour aider à caractériser l'efficacité des algorithmes, mais la notion de meilleur / moyen / pire cas n'est pas liée à la théorie des taux de croissance décrite ici.

Pour parler du Big-O d'un algorithme, il faut s'engager dans un modèle mathématique spécifique d'un algorithme avec exactement un paramètre n, qui est censé décrire la «taille» de l'entrée, dans tous les sens utiles. Mais dans le monde réel, les intrants ont beaucoup plus de structure que leur longueur. Si tel était un algorithme de tri, je pouvais nourrir dans les cordes "abcdef", "fedcba"ou "dbafce". Tous sont de longueur 6, mais l'un d'eux est déjà trié, un est inversé et le dernier n'est qu'un pêle-mêle aléatoire. Certains algorithmes de tri (comme Timsort) fonctionnent mieux si l'entrée est déjà triée. Mais comment intégrer cette inhomogénéité dans un modèle mathématique?

L'approche typique consiste à simplement supposer que l'entrée provient d'une distribution aléatoire et probabiliste. Ensuite, vous faites la moyenne de la complexité de l'algorithme sur toutes les entrées de longueur n. Cela vous donne un modèle de complexité de cas moyen de l'algorithme. À partir de là, vous pouvez utiliser les notations Big-O / Θ / Ω comme d'habitude pour décrire le comportement moyen des cas.

Mais si vous êtes préoccupé par les attaques par déni de service, vous devrez peut-être être plus pessimiste. Dans ce cas, il est plus sûr de supposer que les seules entrées sont celles qui causent le plus de problèmes à votre algorithme. Cela vous donne un modèle de complexité du pire des cas de l'algorithme. Ensuite, vous pouvez parler de Big-O / Θ / Ω, etc. du modèle le plus défavorable .

De même, vous pouvez également concentrer votre intérêt exclusivement sur les entrées avec lesquelles votre algorithme a le moins de problèmes pour arriver à un modèle dans le meilleur des cas , puis regardez Big-O / Θ / Ω, etc.