Quelqu'un peut-il simplement m'expliquer ce que signifie par le meilleur, le cas pire et moyen de fonctionnement d'un algorithme ???
6 Réponses :
Dans les termes les plus simples, pour un problème où la taille d'entrée est n em>: meilleur cas strong> = temps le plus rapide à compléter, avec des entrées optimales choisies. pire cas fort> = temps le plus lent à compléter, avec des entrées pessimales choisies. cas moyen fort> = moyenne arithmétique. Exécutez l'algorithme plusieurs fois, en utilisant de nombreuses entrées de taille n em> qui proviennent de certaines distributions qui génèrent ces entrées (dans le cas le plus simple, toutes les entrées possibles sont également probables), calculer le temps de fonctionnement total ( en ajoutant les temps individuels) et divisez par le nombre d'essais. Vous devrez peut-être également normaliser les résultats en fonction de la taille des ensembles d'entrée. P> LI>
ul> La complexité et le temps de fonctionnement sont souvent exprimés dans "Big O Notation", qui est utilisé pour décrire la quantité approximative de la durée d'un algorithme requise, basée sur la taille de son entrée. Rob Bell a écrit un Excellent aperçu avec des exemples très clairs. p> Les grosses descriptions les plus couramment utilisées sont p> Vous pouvez voir à partir du tableau ci-dessous que la différence est petite pour de petites tailles d'entrée, mais elle peut devenir formidable que la taille d'entrée augmente même un peu. P>
Par exemple, le meilleur cas pour un algorithme de tri serait des données déjà triées. P> li>
Par exemple, le pire des cas d'un algorithme de tri pourrait être des données triés dans l'ordre inverse (mais cela dépend de l'algorithme particulier). P> li>
Input Size Time to Complete
O(1) O(logN) O(N) O(N2) O(2N)
1 1 1 1 1 1
2 1 2 2 4 4
4 1 3 4 16 16
8 1 4 8 64 256
16 1 5 16 254 65536
Et faux. Tout d'abord, tous les trois sont w.R.t une taille d'entrée fixe n . Sinon, "pire" ou "meilleur" pourrait ne pas être bien défini. Deuxièmement, des moyens moyens moyens de prendre la moyenne sur toutes les entrées (de cette taille donnée), pondérées avec une distribution de probabilité (généralement uniforme).
Il est également important de noter que le meilleur cas ou le pire cas n'a rien à voir avec la taille d'entrée. Cela a à voir avec la nature de l'entrée. Par exemple. si la liste est déjà triée.
Le meilleur moment serait comme si quelque chose est déjà trié, alors aucun travail n'a besoin d'être fait. Le pire des cas (dépend de votre algorithme), mais réfléchissez à ce que votre algorithme prendrait la plus longue durée.
Pensez à un algorithme en tant que programme. Ce programme prend certaines données, ce qui se rend un moment pendant un moment, puis crache une réponse. Bien sûr, nous nous soucions de la durée pendant laquelle le programme est tombé sur les données avant de donner la réponse.
Mais il y a une prise: pour de nombreux algorithmes, le temps de fonctionnement dépend des données elles-mêmes. De nombreux algorithmes de tri sont plus rapides pour les données déjà triées, par exemple, et certaines sont plus lentes pour les données triés dans l'ordre inverse.
Pensons à ce que ces données viennent de. Peut-être que votre meilleur ami reçoit les données. Votre ami choisit des données qui provoquent votre programme de fonctionner rapidement et que nous appelons cet exécution le meilleur cas, car l'algorithme ne fera jamais mieux que cela. Peut-être que votre pire ennemi (dans des manuels scolaires, cela s'appelle l'adversaire) pour choisir les données. Votre pire ennemi choisit des données qui provoquent votre programme de fonctionner lentement et que nous appelons ce temps d'exécution au pire des cas car l'algorithme ne fera jamais pire que cela. Et peut-être qu'une roue de roulette géante obtient vos données. Ensuite, vous pouvez exécuter votre algorithme sur une bouquet de données de roue de roulette et moyennant tous les travaux pour obtenir la durée de cas moyenne.
::::: ... merci pour la réponse et m'aidez-moi :)
L'heure d'exécution d'un algorithme dépend de la taille et de la "complexité" de l'entrée.
Par exemple, le meilleur cas Temps d'insertion Trier sur une entrée de la taille n est proportionnelle à n , c'est-à-dire C * n unités de temps pour une constante c qui dépend du coût (temps) de comparaison, de l'arithmétique, de ... de votre modèle informatique. Le pire des cas temps d'exécution de cet algorithme (type d'insertion) est proportionnel à n * n . Pour faire une déclaration pour le temps moyen Si vous en savez plus sur les données d'entrée, par exemple. qu'il est trié avec des valeurs décroissantes (et nous trions avec des valeurs croissantes), le temps d'exécution moyen est la Stille proportinne à N * N, mais le facteur constant est plus élevé (car le temps de recherche moyen pour le minimum (qui sera inséré à la la fin de la sous-liste triée) prend plus de temps).
Un autre exemple plus complexe est QuicksTort: sa meilleure heure de fonctionnement pour les données aléatoires est proportionnelle à n * log n . La pire heure de la caste est toujours n * n (souvent pour une entrée déjà triée, mais cela dépend de l'algorithme pour trouver l'élément de pivot dans l'étape de la division).
Le pire des cas est généralement désigné par la notation asymptotique I.e BIG (O)
Le meilleur cas est désigné par la notation asymptotique I.e Big (Omega)
Analyse pire des cas (généralement faite)
Dans la pire analyse de cas, nous calculons la limite supérieure de l'heure d'exécution d'un algorithme. Nous devons connaître l'affaire qui provoque l'exécution du nombre maximal d'opérations. Pour la recherche linéaire, le pire cas se produit lorsque l'élément à rechercher (X dans le code ci-dessus) n'est pas présent dans le tableau. Lorsque X n'est pas présent, les fonctions de recherche () les compare à tous les éléments d'ARR [] un par un. Par conséquent, la complexité du pire des cas de la recherche linéaire serait θ (n).
Analyse moyenne moyenne (parfois faite)
Dans une analyse de cas moyenne, nous prenons toutes les entrées possibles et calculez la durée informatique pour toutes les entrées. Somme toutes les valeurs calculées et diviser la somme par nombre total d'entrées. Nous devons connaître la répartition (ou prédire) les cas. Pour le problème de recherche linéaire, supposons-nous que tous les cas sont uniformément distribués (y compris le cas de x non présumé dans la matrice). Nous résumons donc tous les cas et divisons la somme de (n + 1). Voici la valeur de la complexité moyenne du temps de cas.
J'ai supprimé la balise "Systèmes d'exploitation", car cela ne fait rien avec la question.
Oui ... mais je n'ai pas pu trouver une réponse parfaite