Tout en répondant à Cette question Un débat a commencé dans des commentaires sur la complexité de la complexité de Tri rapide. Ce que je me souviens de mon temps universitaire, c'est que Quicksort est Ce dont j'ai besoin est une explication mathématique correcte de la signification de Ce dont je me souviens si cela définissait la complexité moyenne, vous devez envisager la complexité de l'algorithme pour toutes les intrants possibles, compter le nombre de cas dégénérants et normaux. Si le nombre de cas dégénérants divisé par N tendez-en à 0 lorsque n obtenez-en gros, vous pouvez parler de la complexité moyenne de la fonction globale des cas normaux.
Cette définition est-elle droite ou la définition de la complexité moyenne différente? Et si c'est correct, quelqu'un peut-il l'énoncer plus rigoureusement que moi? O (n ^ 2) dans le pire des cas, O (n journal (n)) dans un cas moyen et O (n journal (n)) (mais avec une liaison plus serrée) dans le meilleur cas.
Complexité moyenne pour expliquer clairement ce qu'il est sur quelqu'un qui croit que la notation Big-O ne peut être utilisée que pour le pire des cas. < / p>
5 Réponses :
L'analyse moyenne des cas est la suivante:
Prenez toutes les entrées d'une longueur fixe (disons Le problème est que vous devrez probablement énumérer toutes les entrées de longueur n ), résumez toutes les heures d'exécution de toutes les instances de cette longueur et construisez la moyenne.
n afin de trouver une complexité moyenne.
Je pense que votre définition est correcte, mais vos conclusions sont erronées.
Ce n'est pas nécessairement vrai que si la proportion de "mauvais" cas a tendance à 0, la complexité moyenne est égale à la complexité de la "normale" cas.
Par exemple, supposons que les cas 1 / (n ^ 2) sont "mauvais" et le reste "normal" et que "les cas" mauvais "prennent exactement (N ^ 4), tandis que" Les "cas" normaux prennent exactement n opérations.
puis le nombre moyen d'opérations requises est égal à: cette fonction est O (n ^ 2) , mais pas O (n). En pratique, cependant, vous pourriez trouver que le temps est polynomial dans tous les cas et que la proportion de "mauvais" cas rétrécit de manière exponentielle. C'est à ce moment-là que vous ignoreriez les mauvaises cas dans le calcul d'une moyenne.
Ok, je suis d'accord avec toi. Je fais vraiment exactement ce que vous suggérez de calculer la complexité de la moyenne. C'est même le calcul que j'avais mis en communication de la question liée. J'étais trop rapide en disant que nous gardons le cas normal, ce qui n'est évidemment pas toujours vrai et dépend de la complexité des cas dégénérateurs. A déclaré comme je l'ai fait, le mauvais cas pourrait même continuer à toujours et que le programme ne s'arrête jamais et ce n'est certainement pas bon pour la moyenne.
@Kriss: Oui, le boîtier non halein est un exemple plus simple que le mien, bien que ce ne soit pas techniquement un "algorithme" que vous analysez.
Si vous recherchez une définition formelle, alors:
La complexité moyenne est le attendu TIME pour une entrée aléatoire.
citation s'il vous plaît. L'article Wiki ne concerne pas vraiment directement.
effectivement trouvé, il en.wikipedia.org/wiki/avery-case_complexity , +1 pour Votre réponse, semble-t-il (si nous croyons Wikipedia), cette définition formelle est vraiment sur une entrée aléatoire.
Également en ce qui concerne le concept de cas de complexité VS Vérifiez en.wikipedia.org/wiki/best,_worst_and_aver_case_case_ a>; Et aussi il semble que vous utilisez le terme «temps d'exécution» pour la fonction de sélection.
Merci, c'est exactement ce que je cherchais.
@UnReason: J'ai lié aux personnes qui ne savent pas quelle valeur attendue signifie en mathématiques. Vous avez raison que cet article n'est pas lié directement à la question.
Vous avez raison.
Big O (gros thêta, etc.) est utilisé pour mesurer fonctions . Lorsque vous écrivez F = O (g), cela ne comporte pas ce que F et G signifie. Ils pourraient être une complexité moyenne de temps, une complexité patheale, des complexités spatiales, désignant la distribution des nombres premiers, etc.
Complexité pire des cas est une fonction qui prend la taille N et vous dit quel est le nombre maximal d'étapes d'un algorithme donné une entrée de taille n.
Comme vous voyez la plus grande complexité des cas et la moyenne des cas, vous pouvez également utiliser Big O pour exprimer leur croissance.
Ce n'est pas tout à fait raison d'écrire F = O (g) si nous sommes pédants. Big O est un ensemble, nous devrions donc écrire f \ in o (g)
@jlclark: c'est un très forte personnalisé d'écrire = lors de l'utilisation de Big O, voir en.wikipedia.org/wiki/asymptotic_notation#equals_sign ou mathématiques concrets sur la notation asymptotique. En fait, je n'ai jamais vu de manuel qui utilise \ Sauf pour signaler cette pécularité.
Convenu que c'est coutumier - je suis pédant. Cependant, comme le dit Wikipedia, beaucoup considèrent "F = O (G) d'être un abus de notation car les mathématiques pure définissent généralement = d'indiquer une égalité bidirectionnelle. Je suis définitivement dans le camp qui considère cette utilisation de = être plutôt odieuse .
Référons Big O Notation à Wikipedia :
Soit F et G être deux fonctions définies sur un sous-ensemble des nombres réels. One écrit
f (x) = O (g (x)) comme x -> infini si ...Ainsi, quelle est la prémisse de la définition indique que la fonction F doit prendre un numéro comme une entrée et donner un numéro sous forme de sortie. De quel numéro d'entrée parlons-nous? Il est censé un certain nombre d'éléments dans la séquence à trier. Quel numéro de sortie pourrions-nous parler? Cela pourrait être un certain nombre d'opérations effectuées pour commander la séquence. Mais arrêtez. Qu'est-ce qu'une fonction? Fonction dans Wikipedia :
Une fonction est une relation entre un ensemble d'entrées et un ensemble de sorties autorisées avec la propriété que chaque entrée est liée à exactement une sortie .
PRODUIS-NOUS EXACLY ONE SORTIE avec notre défense antérieure? Non, nous ne le faisons pas. Pour une taille donnée d'une séquence, nous pouvons obtenir une large variation de nombre d'opérations. Donc, pour que la définition soit applicable à notre cas, nous devons réduire les résultats optimaux (nombre d'opérations) à une valeur unique. Il peut s'agir d'un maximum ("le pire cas"), un minimum ("le meilleur cas") ou une moyenne.
La conclusion est que parler de l'affaire Meilleur / pire / moyen / moyen est correcte mathématiquement et en utilisant la grosse notation sans celles dans le contexte de la complexité de tri est quelque peu négligée.
D'autre part, nous pourrions être plus précis et utiliser une grande notation thêta au lieu de la grosse notation.
Le paragraphe que vous avez souligné en tant que mauvais état, nous pouvons calculer la limite de la moyenne vers l'infini en utilisant l'expansion de Taylor et en ignorant les termes insignifiants. Bien sûr, la valeur moyenne est affectée et je dirige un cas spécifique lorsque l'étui dégénérateur est pas significatif . Évidemment, ce n'est pas toujours vrai. En d'autres termes, bien sûr la valeur moyenne est toujours définissable, mais cela n'aide pas beaucoup lorsque ce que nous voulons n'est pas définissant il mais informatique IT.
@kriss, je ne comprends tout simplement pas "alors vous pouvez parler de la complexité moyenne de la fonction globale des cas normaux".
Ok, je devrais changer de libellé. Je veux juste dire ignorer le terme tendant vers zéro (cas exceptionnels) et garder uniquement le terme "cas normal".
En ce qui concerne l'argument, je pense que si vous donnez une notation Big-O pour la course à la course et que vous ne le qualifiez pas, vous devriez parler du pire des cas, simplement parce que vous dites que la durée est délimitée par une fonction spécifiée. Big-o. Si le temps est délimité, cela signifie que le pire temps est délimité, par définition de «liée». Si vous dites, "ceci est O (n log n) cas0", cependant, alors c'est bien défini et signifie ce que vous dites dans cette question.
Pourrait être utile d'essayer cstheory.stackexchange.com pour la question
@Chris: Bien que la FAQ de ce site indique que "les problèmes de devoirs typiques des manuels" sont trop basiques, et je pense que cela est à peu près aussi basique que cela.
Vous obtiendrez une page de notation mathématique sur là, pas de débutant amical
@Chris S: Je travaille comme programmeur mais j'ai fait des mathématiques dans mon ancien temps, donc ce n'est pas vraiment un problème pour moi. Mais pour d'autres, cela pourrait en effet être agréable d'avoir quelque chose de plus accessible.