Qu'est-ce que la notation Big Omega?

Semblable à la notation big O, la fonction big Omega (Ω) est utilisée en informatique pour décrire les performances ou la complexité d'un algorithme.

Si un temps d'exécution est Ω (f (n)), alors pour un n assez grand, le temps d'exécution est au moins k⋅f (n) pour une constante k. Voici comment penser à un temps d'exécution qui est Ω (f (n)):

fonction big-oméga

Nous disons que le temps d'exécution est «big-Ω of f (n)». Nous utilisons la notation big-Ω pour les limites inférieures asymptotiques , car elle limite la croissance du temps d'exécution par le bas pour des tailles d'entrée suffisamment grandes.

Différence entre Big O et Big Ω

La différence entre la notation Big O et la notation Big Ω est que Big O est utilisé pour décrire le pire des cas d'exécution d'un algorithme. Mais, la notation Big Ω, d'autre part, est utilisée pour décrire le meilleur temps d'exécution des cas pour un algorithme donné.

Plus d'information:

  • Notation Big-Ω (Big-Omega)
MYCODSCHOOL Analyse de la complexité du temps