Les quantiles KTH d'un ensemble N-Element sont les statistiques de commande K-1 qui divisent le réglage trié dans des ensembles de taille égale K (dans les 1). Donnez un algorithme O (N LG K) pour énumérer les quantiles KTH d'un ensemble.
La solution directe consisterait à sélectionner chaque k, 2k, 3k .. IK le plus petit élément, dont le temps de fonctionnement est O (kN) (k appelant à sélectionner la procédure de O (n)). Mais cela peut être optimisé pour faire mieux que O (kN). Après avoir trouvé la médiane des médianes à l'indice 'i' dans la procédure de sélection, nous faisons l'appel récursif suivant.
Si l'indice de la médiane des médianes I est> K, appelez de manière récursive, sélectionnez le plus petit élément de Kth de la sous-arône gauche A [0 ... I]
Si le i est Les appels récursifs ci-dessus peuvent être modifiés ci-dessus, ce qui permettrait de réduire le facteur «K» à «Log K»?
Si l'indice de la médiane des médianies I est> K, sélectionnez récursivement le plus petit élément de Kth de la sous-arône gauche A [0 ... I] et sélectionnez également récursivement le plus petit élément de N - K [I + 1 ... N].
Si le i est L'appel principal serait simplement sélectionné (A, K, N).
4 Réponses :
Je n'ai pas traversé votre approche, mais c'est une question de Int. aux algorithmes de Cormen. Quoi qu'il en soit, je navette pour une solution moi-même et j'aimerais bien partager ma version de l'algorithme. Essayez de réfuter la correction:
Je suppose que nous avons un algorithme de recherche d'une statistique O (n). Donc, je peux trouver la k-ème statistique dans O (n) heure. Supposons que je dis que je trouverai tous les quantiles N / K K-TH à l'aide de la division et de la conquête de telle sorte que:
Si je n'ai n 'éléments, j'ai divisé la matrice en n' / 2 parties, signalez les quantiles de la limite de la limite pour les deux partitions N '/ 2. Et signaler les quantiles restants récursivement. En substance, ce que je fais, c'est, après partitionnement à l'aide de médiane, j'extraînerai le quantile le plus à gauche de la matrice gauche, quant à la partie la plus à gauche de la cloison droite et après avoir découragé ces tableaux d'algorithme récursivement. Mon analyse de complexité vient être:
t (n, k) = 2 * t (n / 2, k / 2) + O (n).
Cela s'avère être O (Nlogk) car la partie K / 2 convergera plus rapidement, bien que vous souhaitiez résoudre ce problème plus rigoureusement. Nous avons également utilisé que N> K (évident du problème. Notez que la tâche d'extraction de 2 quantitiles et de coupera la matrice sera effectuée dans O (n)
Notez que nous utilisons une partition modifiée donnée un index sur le pivot à utiliser comme dernier paramètre d'entrée.
Vous commencez par la profondeur de l'arborescence de la récursion est sur chaque niveau de l'arborescence de la récursion, il y a θ (n) opérations, la durée de fonctionnement est donc θ (NLGK). < / p> kth-quantiles (A, 1 , n, 1, k-1, k) lg k , depuis la partition est fait autour de la médiane des statistiques de commande données (de i à j).
Nous pouvons utiliser une partition aléatoire au lieu de la partition pour améliorer l'efficacité.
sans perte de généralité, supposons que N et K sont des pouvoirs de 2.
Nous fournissons la première fois la statistique N / 2ème ordre, dans le temps O (n) à l'aide de SELECT, puis réduisez le problème pour trouver les quantiles K / 2ème des plus petits éléments N / 2 et des quantiles K / 2ème de la plus grande n. / 2 éléments.
Soit T (n) désignant le temps qu'il prend l'algorithme pour exécuter l'entrée de la taille n.
de
Ensuite, T (N) = CN + 2T (N / 2) pour un C constant C, et le boîtier de base est T (N / K) = O (1).
Ensuite, nous avons: T (n) ≤ CN + 2T (N / 2) ≤ 2CN + 4T (N / 4) ≤ 3CN + 8T (N / 8). . . ≤ journal (k) cn + kt (n / k) ≤ journal (k) cn + o (k) = O (nlogk).
cc. Manuel de la solution
"" " kth quantiles "" ""
importer aléatoire, mathématiques
Importer selectDetermin_1 comme SD
q = []
def kquants (A, L, R, K) : # O (nlgk) k = 13 a = liste (plage (100)) aléatoire.shauffe (A) kquants (A, 0, len (a) -1, k) q.) # o (klgk) impression ([x pour _, x en q]) def bfkquantile (a, k): #o (kn) impression (bfkquantile ( A, k)) où dselect et partition sont comme dans l'article d'AVI Cohen, renvoyant l'entrée dans A à l'index requis et l'index à laquelle la liste est partitionnée. Je ne pouvais pas faire fonctionner le code précédent afin que je souhaite vérifier si cela est ok
Jusqu'où êtes-vous arrivé avec ceci avant de demander de l'aide?
Downvotes, s'il vous plaît, laissez un commentaire. Je suppose que vous avez bulled la question, car cela ne montre pas ce que User472402 a fait pour le résoudre et où se sont bloqués.
Hai, désolé de ne pas fournir de fond sur l'endroit où je suis coincé. Je suis assez nouveau sur le blog :) La solution en avant du détroit serait de sélectionner chaque k, 2k, .. IK Th ELS. Le temps de fonctionnement serait O (kN). Je pense comment réduire le facteur K pour enregistrer k. Mais je ne reçois rien de concluant. S'il vous plaît faire de l'aide.
Où est-ce situé dans le livre de Cormen?