Aujourd'hui, je cherchais le dernier examen de l'olympiade de l'informatique locale et j'ai trouvé un problème intéressant. En bref, il vous demande, étant donné un tableau entier, compter le nombre d'inversions qu'il a, où une inversion est une paire de indices mais voir les contraintes d'entrée ( i , j tel que i> j et a [i] . De manière informelle, le nombre d'inversions est le nombre de paires hors de l'ordre. Initialement j'ai fait une solution O (n²) (oui, la naïfe), mais voyant qu'il ne correspondrait pas bien à la taille de l'entrée, j'ai pensé au problème un peu plus et je réalisé qu'il est possible de le faire dans O (n log n) heure par une variante de tri de la fusion, qui gère la bonne taille de l'entrée.
n entre les entiers entre 1 et m , et pas de duplicates), je me demandais si ma solution est optimale ou savez-vous si c'est Il y a une autre solution à ce problème qui bat O (n journal n) runtime?
3 Réponses :
Le meilleur résultat de la littérature est un algorithme O (n √ (journal n)) en raison de Chan et Patrascu . Aucune idée de la constante.
Intéressant, j'ai toujours pensé que le problème d'inversion avait la même liaison inférieure que le tri, donc dans ce cas où de nombreux algorithmes linéaires sont disponibles pour trier la même chose à faire avec l'inversion. Quoi qu'il en soit, merci pour votre réponse!
O (n journal n) est le meilleur possible autant que je sache.
Une explication détaillée a été donnée ici:
Si nous supposons que le nombre de bits utilisées pour représenter l'entier est constant (disons 32 ou 64 bits), cela peut être résolu dans O (n) temps.
Voici un exemple de mise en oeuvre Python. P>
p>
def inv_count(a, m=(1<<32)):
if not m or not a:
return 0
count = 0
ones = []
zeros = []
for n in a:
if n & m:
ones.append(n & ~m)
else:
count += len(ones)
zeros.append(n & ~m)
m /= 2
return count + inv_count(ones, m) + inv_count(zeros, m)
print inv_count([1, 2, 3, 4, 5])
print inv_count([5, 4, 3, 2, 1])
Qu'est-ce qu'une inversion? Je vois le terme décrocher ailleurs en ce qui concerne les tableaux, mais je ne peux pas vraiment glaner le sens.
OK - a trouvé la réponse à ma propre question - pour le tableau A, si un [i]> A [i + j] où J> 0, un [i] et un [j] sont une inversion. Juste un terme fantaisie pour deux éléments qui sont «d'ordre naturel» WRT. l'un l'autre.
Oh, désolé, j'aurais peut-être dû m'expliquer à ce sujet.
Qu'est-ce qui serait mieux que O (n log n) dans le monde de l'informatique, à court de O (n)?
@Luiz - Pas de problème, à en juger d'autres messages, je suis le seul à ne pas (pas!) Savoir ce que cela signifie!
Ouais, peut-être une non-comparaison, mais je ne pouvais pas comprendre comment.
Quelles sont les limites sur n et m? Il est possible de faire avec un algorithme similaire à compter Tri dans
O (n * m) , mais il est douteux qu'il va battre leO (n log n) algorithme.1 <= n <= m <= 10 ^ 6. Dans ce cas, ce ne serait pas meilleur que l'algorithme quadratique):