Complexité temporelle du tri rapide en cas de pivot (diviser la liste en 90%:10%) (toujours le plus petit élément pour une profondeur égale)

Question

Quelle est la complexité temporelle de quicksort dans les 2 cas suivants :

1. Pivot divise toujours la liste en un rapport de 9:1.
2. Le pivot est toujours le plus petit élément (pire cas) pour une profondeur paire et l'élément du milieu (meilleur cas) pour une profondeur impaire.

Pour 1, je suppose que nous avons l'équation de récurrence :

F(N) = F(N/10) + F(9N/10) + N

Pour 2,

F(N) = F(N-1) + N if even
F(N) = 2*F(N/2) + N if odd

Ai-je raison avec ces équations et comment puis-je résoudre ces deux équations de récurrence ?

Answer 1

Votre formule est correcte, et les deux cas vous donneront une complexité O(nlogn).

première preuve :

Si vous écrivez l'arbre de récursion pour le premier cas, vous verrez qu'à partir de chaque nœud, vous vous brancherez sur un nœud qui est 1/10 la taille du problème actuel et à l'autre nœud qui est égal à 9/10 de la taille du problème actuel.

il est intuitif que la branche gauche atteindra le cas de base en premier (puisque nous utilisons une plus petite partie du problème dans cette branche) et donc la plus grande complexité sera dans la branche droite.

à chaque fois que vous allez à droite, vous résolvez un plus petit problème qui est 9/10 la taille du problème situé au-dessus de lui (son parent). La question qui se pose est donc de savoir quelle est la profondeur d'un tel arbre (combien de fois puis-je diviser mon problème par un facteur de 10/9 )

il n'est pas difficile de voir que la réponse est :

log(10/9) N

à chaque niveau de l'arbre, nous devons passer par N valeurs (ce qui représente l'ensemble du tableau ou du vecteur), la complexité temporelle est donc de :

N * log(10/9) N = N * (log(2) N / log(10/9)

mais log(10/9) est juste une petite constante, donc la complexité temporelle est :

N * log(2) N

seconde preuve

c'est très similaire à l'autre, dans ce cas la profondeur de l'arbre de récursion sera deux fois plus grande que dans le cas du quicksort parfait (qui est celui où nous obtenons toujours la valeur du milieu comme pivot)

Pour comprendre cela, imaginez simplement que la moitié du temps nous allons atteindre la condition paire, ce qui nous fera diviser le tableau parfaitement ; si une telle condition se produit la moitié du temps, cela signifie que nous diviserons le tableau 2 fois plus que nous ne le ferions dans un monde parfait (le pivot divisera toujours le tableau en deux).

2 * N * log(2) N = N * (log(2) N

référence : https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort

Answer 2

Merci, @BrunoBraga, pour les conseils.

Ce sont mes propres explications que je trouve plus intuitives à comprendre :

Pour le cas 1 :

F(N) = F(9N/10) + F(N/10) + N

Puisque F(N/10) qui est le 10% de la sous-liste se termine toujours avant, nous pouvons donc simplifier le problème à :

F(N) = F(9N/10) + N

En résolvant cette équation, on obtient O(NLogN)

Pour le cas 2 :

Puisque nous savons que le meilleur cas dans lequel le pivot divise la liste en deux moitiés égales a une profondeur de LogN .

Nous pouvons à nouveau simplifier ce problème de telle sorte que ce cas aura une profondeur environ deux fois plus grande que celle de l'étude de l'impact sur l'environnement. LogN . (Puisque la profondeur paire a le pire cas que la longueur de la liste ne diminue que d'un élément).

Ainsi, il aura une complexité temporelle de O(NLogN) également.