È possibile invertire una matrice con spazio aggiuntivo costante?

Question

Diciamo che ho una serie Un con n elementi unici sulla gamma [0, n). In altre parole, ho una permutazione degli interi [0, n).

è possibile trasformare A in B usando O (1) spazio extra (AKA sul posto) tale che B [A [i]] = i?

Ad esempio:

 A     B 
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4] 

Answer 1

Sì, è possibile, con O (n^2) algoritmo di tempo: elemento

asporto all'indice 0, quindi scrivere 0 alla cella indicizzato da quell'elemento . Quindi usa l'elemento appena sovrascritto per ottenere l'indice successivo e scrivere l'indice precedente lì. Continua fino a tornare all'indice 0. Questo è l'algoritmo del ciclo leader.

Quindi fare lo stesso a partire dall'indice 1, 2, ... Ma prima di eseguire qualsiasi modifica, eseguire l'algoritmo del ciclo leader senza alcuna modifica a partire da questo indice. Se questo ciclo contiene un indice al di sotto dell'indice iniziale, basta saltarlo.

---

O questo O (n^3) algoritmo di tempo: elemento

Prendere in corrispondenza dell'indice 0, quindi scrivere 0 alla cella indicizzato da quell'elemento. Quindi usa l'elemento appena sovrascritto per ottenere l'indice successivo e scrivere l'indice precedente lì. Continuare fino a tornare all'indice 0.

Quindi fare lo stesso a partire dall'indice 1, 2, ... Ma prima di eseguire qualsiasi modifica, eseguire l'algoritmo del ciclo leader senza alcuna modifica a partire da tutti gli indici precedenti. Se l'indice corrente è presente in un ciclo precedente, basta saltarlo.

---

ho scritto (leggermente ottimizzata) implementation di O algoritmo (n^2) in C++ 11 per determinare quanti accessi supplementari sono necessari per ogni elemento in media se permutazione casuale è invertita. Ecco i risultati:

size accesses 
2^10 2.76172 
2^12 4.77271 
2^14 6.36212 
2^16 7.10641 
2^18 9.05811 
2^20 10.3053 
2^22 11.6851 
2^24 12.6975 
2^26 14.6125 
2^28 16.0617 

Anche se la dimensione cresce in modo esponenziale, il numero di accessi elemento cresce quasi linearmente, così la complessità orario previsto per permutazioni casuali è qualcosa di simile O (n log n).

Answer 2

L'inversione di un array A ci richiede di trovare una permutazione B che soddisfi il requisito A[B[i]] == i per tutti i.

Per creare l'inverso sul posto, è necessario scambiare elementi e indici impostando A[A[i]] = i per ogni elemento A[i]. Ovviamente, se dovessimo semplicemente ripetere lo A ed eseguire la sostituzione di cui sopra, potremmo ignorare gli elementi imminenti in A e il nostro calcolo fallirebbe.

Pertanto, dobbiamo scambiare elementi e indici lungo i cicli di A seguendo lo c = A[c] fino a raggiungere l'indice iniziale del ciclo c = i.

Ogni elemento di A appartiene a uno di questi cicli. Dato che non abbiamo spazio per memorizzare se un elemento A[i] è già stato elaborato e deve essere saltato, dobbiamo seguire il suo ciclo: se raggiungiamo un indice c < i, sapremmo che questo elemento fa parte di un ciclo precedentemente elaborato.

Questo algoritmo ha un caso peggiore run-time complessità della O (n²), una complessità di run-time media di O (n log n) e un best-case-runtime complessità O (n).

function invert(array) { 
 
    main: 
 
    for (var i = 0, length = array.length; i < length; ++i) { 
 
    
 
    // check if this cycle has already been traversed before: 
 
    for (var c = array[i]; c != i; c = array[c]) { 
 
     if (c <= i) continue main; 
 
    } 
 
    
 
    // Replacing each cycle element with its predecessors index: 
 
    var c_index = i, 
 
     c = array[i]; 
 
    do { 
 
     var tmp = array[c]; 
 
     array[c] = c_index; // replace 
 
     c_index = c; // move forward 
 
     c = tmp; 
 
    } while (i != c_index) 
 
     
 
    } 
 
    return array; 
 
} 
 
    
 
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]

EsempioA = [1, 2, 3, 0]:

1. Il primo elemento all'indice appartiene al ciclo di elementi 1 - 2 - 3 - 0. Una volta che spostiamo gli indici 0, 1, 2 e 3 lungo questo ciclo, abbiamo completato il primo passo.

2. L'elemento successivo all'indice appartiene allo stesso ciclo e il nostro check ci dice così in un solo stadio (dato che è un passo indietro).

3. Lo stesso vale per i restanti elementi e .

   

In totale, eseguiamo 4 + 1 + 1 + 1 'operazioni'. Questo è lo scenario migliore.