trouver le k-ième élément le plus petit dans l'union de deux triées listes de taille m et n avec log d'efficacité (k)

Question

Trouver le k-ième élément le plus petit dans l'union de 2 listes de taille m et n

triés par ordre journal d'efficacité (k) ,, je l'ai fait beaucoup de réflexion et de recherche i également obtenu le

pesedocode et lui expliquer ... jusqu'à présent, je ne comprends toujours pas ou ne comprennent pas le

la question droite .. toute aide sera appréciée ....

Answer 1

Donc, vous devez définir, par exemple { 1, 4, 5, 7, 8, 12, 98, 1993 } et { 2, 5, 8, 10, 88 }. Et vous voulez trouver le troisième plus petit élément.

Cela signifie m = 8, n = 5 et k = 3. L'inspection visuelle de ces ensembles, vous verrez que la réponse est 4. Votre algorithme de recherche doit trouver la valeur correcte dans O(log(k)) (c'est "big O").

Cela signifie que si votre algorithme trouve l'élément avec un certain nombre d'étapes N = n1 + n2 + ..., où chacun des n1, n2, ... est fonction de k, le taux de croissance de tous n1, n2... doit être inférieur ou égal au taux de croissance du journal (k).

Si cela n'a pas de sens, essayez de trouver l'élément en moins de k pas (où k> 1).