J'essaie de concevoir un algorithme pour trouver des indices de deux mêmes éléments dans un tableau. L'entrée est une matrice et la sortie est deux indices I & J tels que la matrice [I] = tableau [J]. La complexité du temps doit être O (nlogn).
Voici ce que j'ai essayé boucle imbriquée est O (n ^ 2), mais si j'essaie de concevoir comme ça . Quelle serait la complexité du temps? n est la taille de la matrice
Ma mise en œuvre fonctionnerait O (N [(N-1) + (N-2) + (N-3) ... + 1]). Est-ce toujours (n ^ 2), quelqu'un m'a dit que c'est O (nlogn), pourquoi?
3 Réponses :
Comme vous savez que la complexité temporelle de votre algorithme est Si vous triez le tableau, deux indices avec la même valeur pourraient être situés à côté de l'autre. Par conséquent, vous pouvez parcourir la matrice triée et signaler leur index initial des deux indices de voisins actuels dans la matrice triée.
La complexité temporelle du tri pourrait être O (n ^ 2) . Pour obtenir un meilleur résultat, vous pouvez d'abord trier le tableau, puis trouver les indices.
O (n log n) , puis itération sur la matrice est o (n) . Par conséquent, cet algorithme est O (n journal n) .
Vous pouvez conserver deux array: une avec les valeurs ( J'ai implémenté cette idée dans une fonction Python: Vous pouvez essayer avec quelques exemples: A ) et une avec les indices ( i ). Un éventuel O (nlogn) algorithme pourrait être:
A en parallèle avec la matrice d'index i . (Complexité temporelle: O (nlogn) ).
A et comparez tous les éléments avec son voisin droit, si un duplicata est trouvé, vous pouvez renvoyer l'index correspondant dans i . (Complexité temporelle: O (n) )
a = [2,3,5,2,6] donner (0, 3)
a = [2, 3, 100, 6, 15, 40, 7, 3] donner (1, 7)
Vous pouvez utiliser une carte pour la recherche inverse pour boucle a o (n) heure + inverselookup a O (1 ) Heure + O (n) Espace (Table de hachage)