Python - Types d'algorithmes

L'efficacité et la précision des algorithmes doivent être analysées pour les comparer et choisir un algorithme spécifique pour certains scénarios. Le processus de réalisation de cette analyse est appelé analyse asymptotique. Il se réfère au calcul du temps d'exécution de toute opération en unités mathématiques de calcul. Par exemple, le temps d'exécution d'une opération est calculé comme f (n) et peut être pour une autre opération, il est calculé comme g (n2). Cela signifie que le temps de fonctionnement de la première opération augmentera linéairement avec l'augmentation de n et le temps de fonctionnement de la deuxième opération augmentera de façon exponentielle lorsque n augmente. De même, le temps d'exécution des deux opérations sera presque le même si n est significativement petit.

Habituellement, le temps requis par un algorithme relève de trois types -

  • Meilleur cas - Temps minimum requis pour l'exécution du programme.
  • Cas moyen - Temps moyen requis pour l'exécution du programme.
  • Pire cas - Temps maximum requis pour l'exécution du programme.

Notations asymptotiques

Voici les notations asymptotiques couramment utilisées pour calculer la complexité du temps d'exécution d'un algorithme.

  • Ο Notation
  • Notation Ω
  • Notation θ

Big Oh Notation, Ο

La notation Ο (n) est la manière formelle d'exprimer la limite supérieure du temps d'exécution d'un algorithme. Il mesure la complexité temporelle du cas le plus défavorable ou la durée la plus longue qu'un algorithme peut prendre pour se terminer.

Par exemple, pour une fonction f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Notation oméga, Ω

La notation Ω (n) est la manière formelle d'exprimer la borne inférieure du temps d'exécution d'un algorithme. Il mesure la meilleure complexité temporelle du cas ou le meilleur temps qu'un algorithme peut prendre pour se terminer.

Par exemple, pour une fonction f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Notation thêta, θ

La notation θ (n) est la manière formelle d'exprimer à la fois la borne inférieure et la borne supérieure du temps d'exécution d'un algorithme. Il est représenté comme suit -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Notations asymptotiques courantes

Voici une liste de quelques notations asymptotiques courantes -

constant - Ο (1)
logarithmique - Ο (log n)
linéaire - Ο (n)
n log n - Ο (n log n)
quadratique - Ο (n 2 )
cubique - Ο (n 3 )
polynôme - n Ο (1)
exponentiel - 2 Ο (n)