Possiamo calcolare questo in meno di O (n * n) ... (nlogn o n)

https://stackoverflow.com/questions/3659506

01-10-2019
|

Domanda

Questa è una domanda posta a me da un molto molto famoso MNC. La domanda è la seguente ...

Input una matrice 2D N * N di 0 e di 1. Se A (i, j) = 1, allora tutti i valori corrispondenti alla esima riga e la colonna j-esima stanno per essere 1. Se esiste già un 1, rimane come 1.

Ad esempio, se abbiamo l'array

dovremmo ottenere l'output come

La matrice di ingresso è scarsamente popolata.

Questo è possibile in meno di O (N ^ 2)?

Nessuno spazio aggiuntivo è prevista era un'altra condizione. Vorrei sapere se c'è un modo per raggiungere la complessità utilizzando uno spazio <= O (N).

P.S: Non ho bisogno di risposte che mi danno una complessità di O (N * N). Questo non è un problema a casa. Ho provato tanto e non sono riuscito a ottenere una soluzione adeguata e pensato che avrei potuto ottenere alcune idee here.Leave la stampa da parte per la complessità

La mia idea di massima era quella di eliminare può essere dinamicamente il numero di elementi attraversati limitandole a circa 2N o giù di lì. Ma non ho potuto ottenere una vera e propria idea.

Soluzione 7

ragazzi HII,

grazie al commento da MB14 credo che avrei potuto ottenerlo risolto in meno di O (N N) tempo ... La cosa peggiore sarebbe prendere O (N N) ...

In realtà, abbiamo l'array dato supporre

Consente avere 2 array di dimensione N (questo sarebbe il caso peggiore) ... Una è dedicata per righe di indicizzazione e altre colonne ... Mettere quelli con a [i] [1] = 0 in un array e poi un [1] [j] = 0 in un altro ..

Dai quei valori solo e verificare la seconda riga e colonne ... In questo modo, si ottengono i valori di righe e colonne in cui solo 0 ci sono; 's interamente ...

Il numero di valori nella matrice fila dà il numero di 0 nella matrice risultato ed i punti di un [valori di riga-array] [valore di matrice colonna] ti dà i punti ....

potrebbe risolvere in seguito O (N N) e la cosa peggiore è O (N N) ... Come possiamo seee, gli array (di dimensione N) diminuisce ....

Ho fatto questo per un paio di matrici e ottenuto il risultato per tutti loro ...:)

Si prega di correggere me, se io sono da nessuna parte sbagliata ...

Grazie per tutti i vostri commenti ragazzi ... Siete tutti molto disponibile e ho imparato alcune cose lungo la strada ...:)

Altri suggerimenti

Nel peggiore dei casi, potrebbe essere necessario ginocchiera N * N - N bit da 0 a 1 per generare l'output. Sembrerebbe che stai abbastanza bene bloccato con O (N * N).

immagino che si può ottimizzare per il caso migliore, ma sono tentato di dire che il vostro caso peggiore è ancora O (N * N): Il tuo caso peggiore sarà un array di tutti 0, e vi deve esaminare ogni singolo elemento.

L'ottimizzazione comporterebbe saltare una riga o colonna non appena avete trovato un "1" (posso fornire dettagli, ma ha detto che non si cura di O (N * N)", ma se non hai i metadati per indicano che un'intera riga / colonna è vuota, o se non si dispone di un modo di stile SIMD per controllare campi multipli in una sola volta (per esempio, se ogni riga è allineato per 4, e si può leggere 32 bit di dati vale la pena, o se i dati sono sotto forma di una maschera di bit), si avrà sempre a che fare con il problema di una matrice tutto da zero.

Chiaramente, né la matrice di uscita né la sua versione negata deve essere sparso (prendere una matrice con la metà del primo insieme riga 1 e quant'altro a 0 vedere), così tempo dipende quale formato si è permesso di utilizzo per l'uscita. (Sto assumendo l'input è una lista di elementi o qualcosa di equivalente, perché altrimenti non si poteva approfittare della matrice essere sparsa.)

Una soluzione semplice per O (M + N) spazio e tempo (M è il numero di quelle della matrice di input): prendere due array di lunghezza N riempito con quelli, scorrere tutti quelli nell'input, e per ogni goccia coordinata X della prima matrice e Y dal secondo. L'uscita è due array, che definiscono chiaramente la matrice risultato. Sua (X, Y) coordinate è 0 se e solo se la coordinata X della prima matrice e la coordinata Y del secondo sono 0

Aggiornamento: a seconda della lingua, si potrebbe usare qualche trucchetto per restituire una matrice normale 2D facendo riferimento alle più volte stessa riga. Per esempio in PHP:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

Naturalmente questa è una matrice normale solo finché non si tenta di scrivere.

Dato che ogni ingresso della matrice deve essere controllato, il tuo caso peggiore sta andando sempre essere N * N.

Con un piccolo 2 * N archiviazione aggiuntivo, è possibile eseguire l'operazione in O (N * N). Basta creare una maschera per ogni riga e un altro per ogni colonna - la scansione della matrice e aggiornare le maschere, come si va. Quindi eseguire la scansione di nuovo per popolare la matrice risultato in base alle maschere.

Se stai facendo qualcosa in cui la matrice di ingresso sta cambiando, è possibile memorizzare un conteggio di non-zero voci per ogni riga e colonna dell'ingresso (piuttosto che una maschera semplice). Poi, quando una voce nel ingresso cambia, si aggiornano i conteggi di conseguenza. A quel punto, vorrei cadere la matrice di uscita del tutto e interrogare le maschere / conta direttamente piuttosto che pur mantenendo la matrice di uscita (che potrebbe anche essere aggiornato come il cambiamento cosa in meno di N tempo N se si voleva davvero per mantenerlo in giro). Così si carica la matrice iniziale sarebbe ancora O (N N), ma gli aggiornamenti potrebbe essere molto meno.

La matrice di ingresso può essere scarsa, ma a meno che non si può ottenere in un formato sparse (vale a dire un elenco di coppie (i,j) che vengono inizialmente impostato), basta leggere il vostro ingresso consumerà O (n ^ 2) tempo. Anche con ingresso sparso, è facile finire con O (n ^ 2) uscita scrittura. Come un trucco, se si era permesso di produrre un elenco di righe e colonne set set, allora si potrebbe scendere a tempo lineare. Non c'è nessuna magia per essere avuto quando l'algoritmo è in realtà per produrre un risultato più sostanzioso di 'sì' o 'no'.

commento di Mcdowella su un'altra risposta suggerisce un altro formato di ingresso alternativa: codifica run-length. Per un ingresso sparsa, che non più di O (n) richiede ovviamente di leggerlo (considerare quante transizioni sono tra 0 e 1). Tuttavia, da lì si rompe. Si consideri una matrice di input strutturato come segue:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

Cioè, alternando 0 e 1 sulla prima fila, 0 altrove. Chiaramente sparse, poiché ci sono quelli n/2 in totale. Tuttavia, l'uscita RLE deve ripetere questo schema in ogni riga, portando a O (n ^ 2) di uscita.

Tu dici:

dovremmo ottenere il risultato come ...

Quindi è necessario uscita l'intera matrice, che ha N ^ 2 elementi. Questo è O (N * N).

Il problema in sé non è O (N * N): Non dovete calcolare e memorizzare l'intera matrice: è necessario solo due vettori, L e C, ciascuno di dimensione N:

L [x] è 1 se la linea x è una linea di quelle, altrimenti 0;

C [x] è 1 se la linea x è una linea di quelle, altrimenti 0;

È possibile costruire questi vettori a O (N), perché la matrice iniziale è scarsa; i dati in ingresso non sarà una matrice, ma una lista contenente le coordinate (riga, colonna) di ciascun elemento diverso da zero. Durante la lettura di questo elenco, insieme L [online] = 1 e C [colonna] = 1, e il problema è risolto: M [l, c] == 1 se L [l] == 1 O C [c] = = 1

C'è chiaramente fino a lavoro O(N^2) da fare. Nella matrice

tutti i bit devono essere impostato a 1, e N*(N-1) non è impostato su uno (20, in questo caso 5x5).

Al contrario, si può trovare con un algoritmo che fa sempre in tempo O(N^2): somma lungo la riga superiore e lasciare che della colonna, e se la riga o la colonna ottiene una risposta diversa da zero, compilare l'intera riga o colonna; quindi risolvere il più piccolo (N-1) x (N-1) problema.

Quindi, esistono casi che devono avere almeno N^2 e comunque può essere risolto in N^2 senza spazio aggiuntivo.

Se la matrice è scarsa, la complessità dipende molto dalla codifica di ingresso e la sua in particolare non ben misurata in NN ² o qualcosa di simile, ma in termini di N l'immissione complessità M ⁱⁿ e l'output complessità M ^out. Mi aspetto qualcosa di simile a O (N + M ^a + M ^out), ma molto a seconda della codifica e trucchi che si può giocare con esso.

Questo dipende interamente della vostra struttura di dati in ingresso. Se si passa tua matrice (1 e 0), come una matrice 2D è necessario attraversare e che è O (n ^ 2). Ma, come i dati è scarsa, se si passa solo il 1 di come input, si può fare in modo che l'ouptut è O (M), dove M non è il numero di cellule, ma il numero di cellule 1. Sarebbe qualcosa di simile a questo (pseudocodice sottostante):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

Non riempire il centro della matrice quando si sta controllando i valori. Come si passa attraverso gli elementi, quando si ha 1 impostare l'elemento corrispondente nella prima riga e nella prima colonna. Poi tornare indietro e riempire il basso e attraverso.

modifica:. In realtà, questo è lo stesso di Andy

Dipende dalla vostra struttura di dati.

Ci sono solo due casi possibili per le righe:

una riga i è riempito di 1 di se c'è un elemento (i, _) in ingresso
Tutte le altre righe sono gli stessi: cioè il j-esimo elemento è 1 se e solo se esiste un elemento (_, j) in ingresso

Quindi il risultato potrebbe essere rappresentato compatto come un array di riferimenti alle righe. Poiché abbiamo solo bisogno di due righe il risultato sarebbe anche solo consumare O memoria (N). A titolo di esempio, questo potrebbe essere implementato in Python come segue:

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

Una chiamata campione non sia

 f([(1,1),(2,2),(4,3)],5)

con il risultato

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

Il punto importante è che gli array non vengono copiati qui, cioè M [riga] = A è solo un'assegnazione di un riferimento. Da qui la complessità è O (N + M), dove M è la lunghezza dell'input.

#include<stdio.h>

includere

int main () { int arr [5] [5] = {{1,0,0,0,0}, {0,1,1,0,0}, {0,0,0,0,0}, {1,0,0,1,0}, {0,0,0,0,0}}; int var1 = 0, var2 = 0, i, j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

Questo programma si avvale di soli 2 4 variabili temporanee (var1, var2, i e j) e, quindi, viene eseguito nello spazio costante nel tempo la complessità O (n ^ 2) .. penso che non è possibile a tutti per risolvere questo problema in

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow