Complexité de l'application d'une permutation sur place

À ma grande surprise, je n'ai pas pu trouver de documents à ce sujet - probablement recherché les mauvais mots clés.

Donc, nous avons un tableau de tout, et une fonction sur ses indices; f est une permutation.$f$$f$

Comment réorganiser le tableau selon avec une mémoire et une exécution aussi proches que possible de O ( 1 ) et O ( n ) ?$f$$O(1)$$O(n)$

Y a-t-il des conditions supplémentaires lorsque cette tâche devient plus facile? Par exemple, lorsque nous savons explicitement qu'une fonction est l'inverse de f ?$g$$f$

Je connais un algorithme qui suit les cycles et parcourt un cycle pour chaque index pour vérifier s'il est le moins dans son cycle, mais encore une fois, il a le pire cas d' exécution , bien qu'en moyenne il semble se comporter mieux. ..$O(n^2)$

$O(n \log n)$$O( \log^{2} n )$

Option 1: trichez en compressant votre permutation en une structure de données succincte, voir Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2: utilisez une décomposition de cycle primaire pour stocker la perm succinctement et utilisez cet espace supplémentaire pour tricher http://oeis.org/A186202

$O(n^2)$$O(\#\text{cycles} * \log n)$

$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$$O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

$i = 1 .. n$$p(i)$$i$$O(n^2)$$O(\log n)$

Si vous utilisez la représentation du cycle de la permutation, vous avez besoin d'un élément de tableau supplémentaire pour stocker l'élément en cours de permutation et vous pouvez parcourir les cycles dans au pire les opérations O (N).

Toute permutation de N éléments peut être convertie en toute autre permutation en utilisant N-1 ou moins d'échanges. Le pire des cas pour cette méthode peut nécessiter des appels O (n ^ 2) vers votre oracle, F (). Commencez par la moindre position. Soit x la position que nous échangeons actuellement.

Si F (x)> = x, permutez les positions x et F (x). Sinon, nous devons trouver où l'élément qui était en position F (x) est actuellement dans la liste. Nous pouvons le faire avec l'itération suivante. Soit y = F (x). Faire jusqu'à y> = x: y = F (y): Fin Do. Échangez maintenant les positions x et y.

Cette méthode utilise l'inverse de F et nécessite n bits de stockage. Si x est la position d'un élément dans le tableau d'origine, soit G (x) la position de l'élément dans le tableau trié. Soit B un tableau de n bits. Réglez tous les n bits de B sur 0.

POUR x = 1 à n-1: SI B (x) == 0 ALORS: y = G (x): FAIRE JUSQU'À x == y: Inverser les positions x et y: B (y) = 1: y = G ( y): BOUCLE: ENDIF: SUIVANT X

Cette méthode continue de permuter l'élément actuellement en position x à la position finale de l'élément. La boucle intérieure se termine lorsque l'élément correct est échangé en position x. Étant donné que chaque échange déplace au moins un élément vers sa position finale, la boucle intérieure Do ne peut pas s'excuser plus de n-1 fois pendant l'exécution. Je pense que cette méthode est O (n) temps et espace.