Est-ce correct ou incorrect de dire qu'une entrée indique que $ C $ provoque une période d'exécution moyenne d'un algorithme?

Question

Je traversais le texte Introduction à l'algorithme de Cormen et. Al. où je suis tombé sur un extrait que j'ai eu besoin d'un peu de clarification.

Maintenant, aussi loin que j'ai appris que, tandis que le meilleur cas et et la complexité de temps d'un algorithme surviennent pour une certaine entrée physique à l'algorithme (disons un entrée $ A $ provoque le temps d'exécution du pire des cas pour un algorithme ou dites une entrée $ B $ cause le Le meilleur cas d'exécution d'un algorithme, asymptotiquement), mais il n'existe pas de telle entrée physique qui provoque le temps moyen d'exécution d'un algorithme car le temps d'exécution moyen d'un algorithme est par définition de la durée d'exécution de l'algorithme en moyenne sur toutes les intrants possibles. . C'est quelque chose que j'espère que ce qui n'existe que mathématiquement.

Mais d'autre part, des entrées à un algorithme qui ne sont ni la meilleure entrée de cas ni la pire entrée de cas ne sont censées être quelque part entre les extrêmes et la performance de notre algorithme ne leur est pas mesurée par nul autre que la moyenne Complexité du temps du cas Comme la complexité du temps moyen de l'algorithme se situe entre les pires et les meilleures complexités de cas, tout comme notre contribution entre les deux extrêmes.

est-il correct ou incorrect de dire qu'une entrée indique $ C $ provoque une période d'exécution moyenne d'un algorithme?

L'extrait du texte qui m'a fait poser une telle question est la suivante:

Dans le contexte de l'analyse de Quicksort,

Dans le cas moyen, la partition produit un mélange de diviseurs "bons" et "mauvais". Dans un arbre de récursivité pour une exécution moyenne de partition, les bonnes et les mauvaises divisions sont distribuées au hasard dans l'arbre. Supposons, pour des raisons d'intuition, que le bien et le mauvais divisent des niveaux alternatifs dans l'arbre, et que les bonnes divisions sont les meilleures scissions et que les mauvaises divisions sont les pires scissions. La figure (a) montre les scissions à deux niveaux consécutifs dans l'arborescence de la récursivité. À la racine de l'arbre, le coût est $ n $ pour partitionnement et les compartiments produits ont des tailles $ n- 1 $ et $ 0 $ : le pire des cas. Au niveau suivant, la sous-carré de la taille $ n- 1 $ subit une partitionnement des meilleures cas dans des sous-bras de taille $ (n -1) / 2 - 1 $ et $ (N-1) / 2 $ supposons que le coût de la condition limite est 1 $ $ pour la sous-carré de la taille 0 $ .

La combinaison de la mauvaise séparation suivie de la bonne scission produit trois sous-tableaux de tailles $ 0 $ , $ ( n-1) / 2 - 1 $ et $ (n-1) / 2 $ à un coût de partitionnement combiné de $ \ theta (n) + \ theta (n-1)=theta (n) $ . Certes, cette situation n'est pas pire que celle de la figure (b), à savoir un seul niveau de partitionnement qui produit deux compartiments de taille $ (n-1) / 2 $ , à un coût de $ \ theta (n) $ . Pourtant, cette dernière situation est équilibrée!

Answer 1

Temps de fonctionnement moyen d'un algorithme en ce qui concerne une distribution $ d $ est, par définition , la durée de fonctionnement attendue de l'algorithme lorsqu'il est exécuté sur une entrée échantillonnée selon $ d $ .

Cela doit être contrasté avec temps de fonctionnement le pire de cas , qui est le temps d'exécution maximal sur toute entrée d'une longueur donnée et le meilleur cas de fonctionnement Temps , qui est la durée minimale de fonctionnement de toute entrée de longueur donnée.

Depuis le pire des cas et le meilleur temps de fonctionnement est défini comme maximum et minimum, il y a des intrants les accomplis. Le temps de fonctionnement moyen est une attente, et il n'a donc pas de sens de parler d'une contribution à leur atteindre.

Si vous lancez une matrice, le numéro attendu que vous obtenez est 3.5. Ceci n'est pas atteint par un lancer particulier. Si la matrice avait 5 côtés, le nombre attendu est 3, ce qui correspond à un peu, mais cela ne signifie pas que le lancer est "cas moyen".

---

Qu'est-ce qui arrive parfois, c'est que vous pouvez isoler une classe d'entrées $ x $ tel que lorsqu'il est exécuté sur une entrée de $ X $ , la durée d'exécution de l'algorithme est dans un facteur constant de la durée de fonctionnement moyenne (pour cela pour avoir un sens, $ x / span> devrait réellement correspond à une séquence $ x_n $ d'entrées de chaque longueur, ou au moins infiniment de longueur). Vous pouvez dire que $ x $ "atteint" la durée d'exécution attendue de l'algorithme.