Le meilleur, le pire et le cas moyen temps de course

Pouvez tout simplement m'expliquer ce qu'on entend par Meilleur, le pire et le cas moyen temps d'exécution d'un algorithme ???

Avez-vous essayé de chercher?
J'ai enlevé "systèmes d'exploitation" de la balise, car il ne fait rien à la question.
Oui...mais je ne pouvais pas trouver une réponse parfaite

OriginalL'auteur Grant | 2012-03-05

  1. 25

    Dans les termes les plus simples, pour un problème où la taille de saisie est n:

    • Meilleur des cas = temps le plus rapide à remplir, avec optimale des intrants choisi.

      Par exemple, dans le meilleur des cas pour un algorithme de tri qui seraient données qui sont déjà triées.

    • Pire des cas = plus lent de temps, avec pessimal entrées choisi.

      Par exemple, le pire des cas pour un algorithme de tri pourraient être données triées dans l'ordre inverse (mais cela dépend de l'algorithme).

    • Moyen = moyenne arithmétique. Exécuter l'algorithme plusieurs fois, avec différentes entrées de taille n qui viennent de certains de distribution qui génère ces entrées (dans le cas le plus simple, toutes les entrées possibles sont équiprobables), calculer le temps total d'exécution (en ajoutant le temps), et diviser par le nombre d'essais. Vous pouvez aussi avoir besoin de normaliser les résultats en fonction de la taille de l'entrée de jeux.

    De la complexité et de temps d'exécution sont souvent exprimées en "Big O notation", qui est utilisé pour décrire la quantité approximative de temps un algorithme nécessite de compléter, en fonction de la taille de son entrée. Rob Bell a écrit un excellente vue d'ensemble avec des exemples très clairs de cas.

    Les plus couramment utilisés Big O les descriptions sont

    • O(1) se termine toujours dans environ la même quantité de temps, indépendamment de la taille de saisie.
    • O(logN) prend un fixe laps de temps supplémentaire à chaque fois la taille de saisie en double.
    • O(N) prend deux fois plus de temps pour finir si la taille de saisie en double.
    • O(N2) prend quatre fois plus de temps si la taille de saisie en double.
    • O(2N) augmente de façon exponentielle à mesure que la taille augmente.

    Vous pouvez le voir dans le tableau ci-dessous que la différence est faible pour une petite entrée tailles, mais il peut devenir énorme que la taille de l'image augmente encore un peu.

    Taille de saisie de Temps pour Terminer 
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 le mal. Tout d'abord, tous les trois sont des w.r.t fixe d'entrée de taille n. Sinon, le "pire" ou "meilleur" peut ne pas être bien définis. Deuxièmement, la moyenne des cas moyens de prendre la moyenne sur tous entrées (de cette taille), pondéré avec une certaine distribution de probabilité (généralement uniforme).

    OriginalL'auteur Adam Liss

  2. 3

    Pire Des Cas De L'Analyse (Généralement Le Cas)
    Dans le pire des cas de l'analyse, nous calculons la limite supérieure sur le temps d'exécution d'un algorithme. Nous devons savoir ce qui provoque nombre maximum d'opérations à exécuter. Pour la Recherche Linéaire, le pire des 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, la recherche de fonctions() compare avec tous les éléments d'arr[] un par un. Par conséquent, le pire des cas le temps de la complexité de la recherche linéaire serait Θ(n).

    Moyen de l'Analyse de Cas (Parfois)
    En moyenne, analyse de cas, nous prenons toutes les entrées possibles et calculer les temps de calcul pour toutes les entrées. La somme de toutes les valeurs calculées et diviser la somme par le nombre total d'entrées. Nous devons savoir (ou prédire) la distribution des cas. Pour la recherche linéaire problème, nous supposons que tous les cas sont uniformément distribués (y compris dans le cas de x n'étant pas présent dans le tableau). Nous avons donc la somme de tous les cas et de diviser la somme par le (n+1). Suivant est la valeur de la moyenne de l'étude de cas de la complexité.

    Meilleur Des Cas, L'Analyse De (Faux)
    Dans le meilleur des cas, l'analyse, nous calculons la limite inférieure sur le temps d'exécution d'un algorithme. Nous devons savoir ce qui provoque nombre minimum d'opérations à exécuter. Dans le linéaire du problème de recherche, dans le meilleur des cas se produit lorsque x est présent dans le premier emplacement. Le nombre d'opérations dans le meilleur des cas est constante (ne dépend pas de n). Donc, le temps de la complexité dans le meilleur des cas serait Θ(1)

    OriginalL'auteur samaksh shrivastava

  3. 2

    Penser à un algorithme d'un programme. Ce programme prend certaines données, en bidons sur elle pendant un certain temps, et puis crache une réponse. Bien sûr, nous nous soucions de combien de temps le programme bidons sur les données avant de donner la réponse.

    Mais il y a un hic: pour de nombreux algorithmes, temps d'exécution dépend de la donnée elle-même. De nombreux algorithmes de tri sont plus rapides pour déjà triés, par exemple, et certains sont plus lents pour les données triées dans l'ordre inverse.

    Nous allons donc réfléchir à où que proviennent les données. Peut-être que votre meilleur ami est de choisir les données. Votre ami récupère les données que les causes de votre programme à exécuter rapidement, et nous appelons cela runtime le meilleur des cas, puisque l'algorithme ne fera jamais mieux que ça. Peut-être votre pire ennemi (dans les manuels scolaires, ce qui est appelé l'adversaire) obtient de choisir les données. Votre pire ennemi choisit de données que les causes de votre programme à exécuter lentement, et que nous appelons runtime le pire des cas, car l'algorithme ne fera jamais pire que ça. Et peut-être un géant de la roue de la roulette obtient de choisir vos données. Ensuite, vous pouvez exécuter votre algorithme sur un tas de roue de roulette de données et la moyenne de tous les moteurs d'exécution pour obtenir la moyenne de l'étude de cas.

    :::::...thnnks pour la réponse, & m'aider 🙂

    OriginalL'auteur Adam Mihalcin

  4. 1

    Le meilleur moment serait comme si quelque chose est déjà triés, pas de travail qui doit être fait.
    Le pire des cas (dépend de votre algorithme) mais pensez à ce que serait la cause de votre algorithme pour prendre le plus de temps.

    OriginalL'auteur

  5. 1

    Le temps d'exécution d'un algorithme dépend de la taille et de la "complexité" de l'entrée.

    Par exemple le meilleur des cas temps d'exécution du tri d'insertion sur une entrée de taille n est proportionnelle à n, c'est à dire c * n les unités de temps pour certains constante c qui dépend du coût (en temps) de la comparaison, de l'arithmétique, ... de votre modèle de calcul. Le pire des cas temps d'exécution de cet algorithme (le tri par insertion) est proportionnelle à n * n. De faire une déclaration pour le temps moyen nous avons besoin d'une hypothèse sur la distribution des données d'entrée: E. g. si l'entrée est aléatoire de données (et donc susceptibles de ne pas trié) la moyenne des temps de course est de nouveau proportionnelle à n*n.

    Si vous en savez plus sur les données d'entrée, par exemple, qu'elle est triée avec la décroissance des valeurs (et nous sommes de tri avec l'augmentation des valeurs) de la moyenne des temps d'exécution est stille proportinal à n*n, mais le facteur constant est plus élevé (parce que la moyenne de temps de recherche pour le minimum (qui sera inséré à la fin de la triés sous-liste) prend plus de temps).

    Un autre, exemple plus complexe est quicksort: Sa moyenne et le meilleur temps d'exécution pour des données aléatoires est proportionnelle à n * journal n. Le pire de la caste de l'époque, est toujours n * n (souvent déjà triés à l'entrée, mais cela dépend de l'algorithme pour trouver l'élément pivot dans le fossé de l'étape).

    OriginalL'auteur Stefan

  6. 1

    pire des cas est généralement notée par notation asymptotique je.e gros(O)

    meilleur des cas est représenté par la notation asymptotique je.e gros(OMEGA)

    OriginalL'auteur TANYA