Pouvez-vous m'aider à comprendre cet algorithme?

Question

Je travaille sur une tâche de devoirs et comme un "indice" on nous dit de trouver l'algorithme suivant, puis de le prouver à la réponse nécessaire. Soit L (1), L (2), .., L (k) des listes triées de n éléments chacune. Donnez un algorithme d'espace O (kn logk) prenant en charge l'opération O (log n + t) Locate, qui renvoie l'emplacement de t éléments.

Idéalement, je serai capable d'utiliser cet algorithme pour me donner un aperçu de la réalisation d'une meilleure solution (ce que veut l'affectation), mais cet algorithme moins efficace est censé m'inspirer, mais je ne peux pas comprendre IT out. Des pensées ou savoir ce que cet algorithme est? Merci!

Answer 1

Avez-vous effectué une recherche google pour O (kn logk)? Cela semble être une signature big-O plutôt unique.

Voici mon premier résultat: mergesort ->What is the relation between merges and number of items in a in k-way merge

Answer 2

ehh ... ça ressemble ... à une recherche binaire? Wiki

Answer 3

Probablement pas une fonction de tri puisque vous avez déjà deux listes triées. Cela me semble aussi être une recherche binaire.

Answer 4

Je ne peux pas sembler trouver celui qui donne O (log n + t), mais j'eu une pensée qui pourrait ou ne pourrait pas aider ...

O (log kn k) est la taille d'une table mappant chaque élément possible au numéro de la liste le contenant. Cependant, l'utilisation de cette fonction pour trouver la liste à regarder donne toujours le temps de recherche * O (log n) pour les éléments t, donc ce n'est pas vraiment ce qui est demandé ...

Answer 5

Je pense qu'il vous demande de trouver un algorithme inefficace d'abord, puis l'utiliser pour en faire un algorithme efficace. Cela ressemble à une recherche linéaire de listes, chacune avec une recherche binaire pour les parcourir. Cela nécessitera un espace O (2t), car vous devez copier les "coordonnées" des éléments t.

Answer 6

Même avec cette grosse notation O, je pense que c'est un problème de recherche binaire parce que vous avez les listes triées.

La complexité de l'espace reste la même car il s'agit d'un algorithme de division et de conquête, vous n'aurez donc pas de problème. Pour être très sûr, le t est-il en dehors de la logn, quelque chose comme O ((logn) + t)?