Notation Big o dans la structure de données : tout ce qu'il faut savoir

La notation Big O dans une structure de données est utilisée pour déterminer l'efficacité d'un algorithme, le temps nécessaire pour exécuter la fonction avec la croissance de l'entrée et la façon dont la fonction évolue. La mesure de cette efficacité peut être divisée en deux parties, à savoir la complexité spatiale et la complexité temporelle.

La notation Big O fait référence à la notation mathématique qui agit comme un facteur limitant de toute fonction lorsqu'un argument est plus enclin à pencher vers une valeur spécifique ou l'infini. Il appartient à la catégorie des notations mathématiques inventées par Edmund Landau, Paul Bachmann et d'autres. Par conséquent, il est collectivement appelé la notation Bachmann-Landau ou la notation asymptotique.

Selon la déduction mathématique, deux fonctions, f(n) et g(n) sont définies sur un ensemble de nombres positifs ou réels qui ne sont pas liés. Ici, g(n) est strictement positif pour toute grande valeur de n. Il peut s'écrire de la manière suivante :

f(n) = O(g(n)) où n tend vers l'infini (n → ∞)

Cependant, ici, la supposition de n à l'infini n'est pas exclusivement définie, et l'expression ci-dessus peut donc s'écrire :

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

Ici, f et g sont les fonctions nécessaires qui partent d'entiers positifs vers des nombres réels qui ne sont pas non négatifs.

Par conséquent, les grandes valeurs de n sont désignées par l'asymptotique Big O.

Propriétés de la notation Big O dans la structure de données

L' algorithme Big O dans la structure de données a quelques propriétés obligatoirement requises. Lesdites propriétés essentielles de la notation Big O sont les suivantes :

• Fonction de sommation :
  Si f(n) = f 1 (n) + f 2 (n) + — + f m (n) et f je (n)≤ f je +1(n) ∀ je=1, 2,–, m,
  alors O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Fonction logarithmique :
  Si f(n) = logan et g(n)=logbn,
  alors O(f(n))=O(g(n))
• Multiplication constante :
  Si f(n) = cg(n), alors O(f(n)) = O(g(n)) où c est une constante non nulle.
• Fonction polynomiale:
  Si f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  alors O(f(n)) = O(nm).

Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Explorez nos cours populaires de génie logiciel

Ici, tout en s'adressant à Big O, chaque fonction de journal augmente de la même manière.

Importance de la notation Big O dans l'analyse d'exécution des algorithmes

Les complexités du temps d'exécution le plus défavorable de l'algorithme sont utilisées pour établir des comparaisons et calculer, en particulier dans le cas de l'analyse des performances d'un algorithme. L'ordre de O (1), représenté par le temps d'exécution constant, est le temps d'exécution le plus rapide de l'algorithme - le temps que prend l'algorithme est le même pour différentes tailles d'entrée. Il est important de noter que le temps d'exécution idéal d'un algorithme est le temps d'exécution constant, ce qui est très rarement atteint car le temps d'exécution de l'algorithme dépend de la taille d'entrée de n.

Par exemple:

Comme mentionné ci-dessus, les performances d'exécution d'un algorithme dépendent principalement de la taille d'entrée de n. Élucidons ce fait avec quelques exemples mathématiques pour faire l'analyse d'exécution d'un algorithme pour différentes tailles de n :

• n = 20
  log (20) = 2,996 ;
  20 = 20 ;
  20 log (20) = 59,9 ;
  20 2 = 400 ;
  2 20 = 1084576 ;
  20 ! = 2,432902 + 18 18 ;
• n = 10
  log(10) = 1 ;
  10 = 10 ;
  10 log (10) = 10 ;
  10 2 = 100 ;
  2 10 = 1024 ;
  dix! = 3628800 ;

Les performances d'exécution d'un algorithme sont calculées de la même manière.

Voici quelques autres exemples algorithmiques d'analyse d'exécution -

• En ce qui concerne la recherche linéaire, la complexité d'exécution est O(n).
• La complexité d'exécution est O(log n) pour la recherche binaire.
• Pour le tri par sélection, le tri à bulles, le tri à compartiments, le tri par insertion, la complexité d'exécution est O(n^c).
• En ce qui concerne les algorithmes exponentiels tels que la tour de Hanoï, la complexité d'exécution est O(c^n).
• Pour Merge SortSort et Heap Sort, la complexité d'exécution est O(n log n).

Comment Big O analyse-t-il la complexité de l'espace ?

Déterminer à la fois la complexité spatiale et d'exécution d'un algorithme est une étape essentielle. En effet, nous pouvons déterminer le temps d'exécution d'un algorithme en analysant les performances d'exécution de l'algorithme et l'espace mémoire que l'algorithme utilise grâce à l'analyse de la complexité spatiale de l'algorithme. Par conséquent, pour mesurer la complexité spatiale d'un algorithme, nous devons comparer les performances de complexité spatiale dans le pire des cas de l'algorithme.

Pour déterminer la complexité spatiale d'un algorithme, nous devons suivre ces deux tâches -

Tâche 1 : Il est vital d'implémenter le programme pour un algorithme particulier.

Tâche 2 : Il est essentiel de connaître la taille de l'entrée n pour déterminer la mémoire que chaque élément contiendra.

Ces deux tâches essentielles doivent être accomplies avant de calculer la complexité spatiale d'un algorithme.

Exemples d'algorithmes de complexité spatiale

Il existe de nombreux exemples d'algorithmes à complexité spatiale, dont certains ont été mentionnés ci-dessous pour une meilleure compréhension de ce type d'algorithme :

• Pour le tri à bulles, la recherche linéaire, le tri par sélection, le tri par insertion, le tri par tas et la recherche binaire, la complexité de l'espace est O(1) .
• La complexité spatiale est O(n+k) en ce qui concerne le tri par base .
• La complexité spatiale est O(n) pour un SortSort rapide.
• La complexité spatiale est O(log n) pour le tri par fusion.

Exemple de notation Big O en C

C'est un fait que la notation Big O est principalement utilisée en informatique pour déterminer la complexité ou les performances d'un algorithme. Cette notation nous permet de classer le comportement des algorithmes en fonction de la croissance de l'espace mémoire ou des exigences de temps d'exécution lorsque l'étendue des données d'entrée devient importante. Il n'est pas conçu pour prédire l'utilisation réelle de la mémoire ou le temps d'exécution, mais pour comparer les algorithmes, puis sélectionner le meilleur d'entre eux pour le travail. Il n'est pas spécifique au langage mais est également implémenté en C.

Ci-dessous, vous trouverez l'algorithme de tri par sélection en C où la complexité dans le pire des cas (notation Big O) de l'algorithme a été calculée : -

for(int i=0; i<n; i++)

{

int min = je ;

for(int j=i; j<n; j++)

{

si(tableau[j]<tableau[min])

min=j;

}

int temp = tableau[i] ;

tableau[i] = tableau[min] ;

tableau[min] = temp ;

}

Pour analyser l'algorithme :

• On peut déjà noter que la plage de la boucle externe for est i < n , ce qui indique que l'ordre de la boucle est O(n).
• Ensuite, nous pouvons identifier qu'il s'agit également de O(n) car j < n pour la boucle for interne.
• La constante est ignorée, même si le rendement moyen est trouvé n/2 pour une constante c. Donc, l'ordre est O(n).
• Après avoir multiplié l'ordre de la boucle interne et de la boucle externe, la complexité d'exécution obtenue est O(n^2).

D'autres algorithmes en C peuvent être facilement implémentés, où les complexités peuvent être facilement analysées et déterminées de la même manière.

Utilisation de la notation Big O

Il existe deux domaines principaux dans lesquels la notation Big O est appliquée : -

• Mathématiques : La notation Big O est assez couramment utilisée dans le domaine des mathématiques pour décrire comment une série finie se rapproche étroitement d'une fonction, en particulier lorsqu'il s'agit des cas d'un développement asymptotique ou d'une série de Taylor tronquée.
• Informatique : C'est un fait bien établi que la notation Big O est principalement utilisée dans le domaine de l'informatique en raison de son utilité dans l'analyse des algorithmes

Cependant, dans les deux applications, la fonction g ( x ) apparaissant dans le O (·) est souvent choisie pour être probablement la plus simple si les termes d'ordre inférieur et les facteurs constants sont omis.

Il existe deux autres usages de cette notation qui sont formellement proches mais relativement différents. Elles sont:-

• Asymptotique infinie
• Asymptotique infinitésimale.

Cependant, cette distinction n'est pas en principe, en application uniquement, la définition formelle du "Big O" étant exactement la même pour les deux cas. La seule différence réside dans les limites de l'argument de la fonction.

Lisez nos articles populaires liés au développement de logiciels

Conclusion

En conclusion, nous pouvons dire que le Big Data joue un rôle essentiel dans les structures de données, et avoir une connaissance approfondie et complète de la notation Big O est un excellent ensemble de compétences à posséder. Il est très demandé dans le secteur de l'emploi et peut être potentiellement un excellent choix pour un cheminement de carrière. Le programme de certificat avancé d'upGrad en Big Data vous donnera l'effet de levier dont vous avez besoin pour dynamiser votre carrière. Il vous présentera les meilleures compétences professionnelles telles que le traitement des données avec PySpark, l'entreposage de données, MapReduce, le traitement du Big Data sur le cloud AWS, le traitement en temps réel, etc.