Comment utiliser les arguments adversaires pour la sélection et le tri par insertion?

On m'a demandé de trouver les arguments adversaires nécessaires pour trouver les limites inférieures pour la sélection et le tri par insertion. Je n'ai pu trouver aucune référence à cela nulle part.

J'ai quelques doutes à ce sujet. Je comprends que les arguments adversaires sont généralement utilisés pour trouver des limites inférieures pour certains "problèmes" plutôt que des "algorithmes".

Je comprends le problème de fusion. Mais comment pourrais-je en écrire un pour le tri par sélection et insertion?

D'après votre commentaire, il semble que vous confondez le sens des limites inférieures, des limites supérieures et de la notation asymptotique. Par exemple, prenez le tri par insertion. Son meilleur temps de fonctionnement est$\Theta(n)$(cela se produit lorsque l'entrée est déjà triée). Son pire temps de fonctionnement est$\Theta(n^2)$(cela se produit lorsque l'entrée est dans l'ordre de tri inverse). Ainsi, puisque le temps de fonctionnement se situe entre une fonction linéaire de$n$ et une fonction quadratique de $n$, vous pouvez dire que le temps d'exécution du tri par insertion est à la fois $\Omega(n)$ et $O(n^2)$. Il est important de comprendre dans ce cas que vous ne pouvez pas dire que le temps de fonctionnement est$\Omega(n^2)$. Pourquoi? Parce qu'il existe une entrée qui provoque l'exécution de l'algorithme$O(n)$. Cependant, vous pouvez dire que le temps d'exécution le plus défavorable est$\Omega(n^2)$, encore une fois parce qu'il existe une entrée qui entraîne l'exécution de l'algorithme $\Omega(n^2)$. Nous utilisons généralement le$O$ notation pour le pire des cas, car nous nous intéressons à une limite supérieure sur le nombre d'opérations effectuées par l'algorithme.

Maintenant, réfléchissons à un argument adverse pour le tri par insertion (vous pouvez essayer d'en dériver un pour le tri par sélection en appliquant les mêmes idées).

Considérez l'algorithme de tri par insertion jouant contre un adversaire que nous appellerons l'adversaire. Le but de l'adversaire est de fournir une entrée X pour l'algorithme qui maximise le nombre de comparaisons effectuées par l'algorithme. Ceci est généralement analysé dans le contexte des arbres de décision . Un arbre de décision montre toutes les séquences de comparaisons possibles que l'algorithme pourrait faire. Chaque nœud intérieur d'un arbre de décision représente une comparaison unique. Les deux enfants d'un nœud représentent les deux résultats de la comparaison (oui / non ou vrai / faux). Chaque feuille représente une sortie possible. Pour les algorithmes de tri, les feuilles sont des permutationsdes clés. L'algorithme commence à la racine et suit un chemin vers une feuille. À chaque nœud interne, la réponse de la comparaison effectuée indique à l'algorithme quel nœud doit être visité ensuite. Lorsque l'algorithme atteint une feuille, il génère sa permutation correspondante. Le temps d'exécution d'un algorithme (vu comme un arbre de décision) pour une entrée donnée est le nombre de comparaisons effectuées dans le chemin de la racine à la feuille de sortie. Maintenant, l'adversaire a une stratégie simple qui fonctionnera contre tout algorithme de tri basé sur la comparaison, y compris le tri par insertion: chaque fois que l'algorithme fait une comparaison, l'adversaire choisit la réponse qui éliminera le moins de permutations possibles.

En général, du fait qu’avec $n$ il y a des éléments $n!$ permutations possibles, tout arbre de décision pour le tri doit avoir au moins $n!$ feuilles, et doit donc avoir de la profondeur $\Omega(\log(n!)) = \Omega(n\log n)$(par approximation de Stirling). Pour le tri par insertion, l'adversaire peut créer une entrée particulière qui fait en sorte que l'arbre de décision correspondant ait une profondeur d'au moins$\Omega(n^2)$.

L'algorithme utilise un tableau $A[1 .. n]$ pour stocker les éléments d'entrée et est basé sur l'invariant suivant:

Au début de chaque itération de la boucle for, le sous-tableau $A[1 .. j-1]$ se compose des éléments originellement $A[1 .. j-1]$, mais dans l'ordre trié.

À chaque itération, les éléments de $A[1 .. j-1]$ sont donc déjà dans l'ordre trié, et l'algorithme examine $A[j]$ et l'insère à sa place finale, en comparant la valeur de $A[j]$ par rapport à la valeur des éléments $A[1 .. j-1]$, a partir de $A[j-1]$ et revenir à $A[j-2]$ et ainsi de suite jusqu'à $A[j]$n'est plus le plus grand de la comparaison. Les éléments$A[j+1 .. n]$ sont dans un état inconnu (en ce qui concerne l'ordre de tri) et seront traités dans des itérations ultérieures.

Voici la stratégie de l'adversaire. Sachant que l'algorithme fonctionne en insérant$A[j]$ à sa place en déplaçant les éléments dans $A[1 .. j-1]$, alors la stratégie évidente est de maximiser $j$-th itération le nombre d'éléments qui doivent être déplacés afin d'accueillir $A[j]$. Ceci est facilement accompli en choisissant soigneusement l'entrée afin qu'elle soit triée dans l' ordre inverse . En effet, dans ce cas, le nombre d'éléments à déplacer à chaque itération est$j-1$. Cela conduit à la$\Omega(n^2)$ pire temps de fonctionnement (déterminé par la série arithmétique correspondante).