Trouver le i-ème élément le plus important

Question

Je souhaite utiliser une procédure Divide-and-Conquer pour calculer le i-ème élément le plus grand d'une rangée d'entiers et analyser la complexité temporelle asymptotique de l'algorithme.

Algorithm ith(A,low,high){ 
    q=partition(A,low,high); 
    if (high-i+1==q) return A[q]; 
    else if (high-i+1<q) ith(A,low,q-1); 
    else ith(A,q+1,high); 
} 

Est-ce vrai? Si oui, comment pourrions-nous trouver sa complexité temporelle?

La complexité temporelle est décrit par la relation de récurrence suivante:

T (n) = T (NQ) + T (q-1) + Θ (n)

Mais comment pouvons-nous résoudre ce relation de récurrence, sans connaître la valeur de q?

Ou y a-t-il un algorithme avec moins de complexité temporelle qui calcule le ième élément le plus grand à une rangée d'entiers?

Answer 1

Ceci est une variante de l'algorithme quick select (qui trouve le plus petit élément i-th plutôt que i-th plus grand élément). Il a un temps de fonctionnement de O(n^2) dans le pire des cas, et O(n) dans le cas moyen.

Pour voir le pire des cas, supposons que vous recherchez le plus grand élément nth, et il arrive que l'algorithme prend toujours q être le plus grand élément de la gamme restante. de sorte que vous appelez la fonction ithn fois. En outre, le sous-programme de partition prend O(n) de sorte que la durée totale est de O(n^2).

Pour comprendre l'analyse de cas moyenne, consultez l'explication fournie par le professeur Tim Roughgarden here.