Algoritmo di moltiplicazione della matrice booleana

Question

Questa è la mia prima domanda su stackoverflow. Ho risolto alcuni esercizi di "Algorithm design" di Goodrich, Tamassia. Tuttavia, sono abbastanza all'oscuro di questo problema. Unusre da dove iniziare e come procedere. Qualsiasi consiglio sarebbe grande. Ecco il problema:

Le matrici booleane sono matrici tali che ciascuna voce è 0 o 1 e la moltiplicazione di matrice viene eseguita utilizzando AND per * e OR per +. Supponiamo di avere due matrici booleane casuali NxN A e B, in modo che la probabilità che qualsiasi voce sia pari a 1 sia 1/k. Mostra che se k è una costante, allora c'è un algoritmo per moltiplicare A e B il cui tempo di esecuzione previsto è O (n^2). Cosa succede se k è n?

Answer 1

moltiplicazione di matrici usando l'approccio iterativo standard è O (n), perché si deve iterare n righe ed n colonne, e per ciascun elemento esegue una moltiplicazione vettore di una delle righe e una delle colonne , che richiede n moltiplicazioni e n-1 aggiunte.

codice Psuedo moltiplicare matrice a per b matrice e memorizza nella matrice c:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     int sum = 0; 
     for(m = 0; m < n; m++) 
     { 
      sum += a[i][m] * b[m][j]; 
     } 
     c[i][j] = sum; 
    } 
} 

Per una matrice booleana, come specificato nel problema, ed è utilizzato in luogo di moltiplicazione e OR al posto di Inoltre, in modo che diventi questo:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     boolean value = false; 
     for(m = 0; m < n; m++) 
     { 
      value ||= a[i][m] && b[m][j]; 
      if(value) 
       break; // early out 
     } 
     c[i][j] = value; 
    } 
} 

la cosa da notare qui è che una volta che il nostro booleano "somma" è vero, siamo in grado di fermare il calcolo e l'inizio fuori dal ciclo più interno, perché ORing i valori successivi con tru Produrrà vero, quindi possiamo immediatamente sapere che il risultato finale sarà vero.

Per qualsiasi costante k, il numero di operazioni prima che possiamo eseguire questa operazione anticipatamente (supponendo che i valori siano casuali) dipenderà da k e non aumenterà con n. Ad ogni iterazione ci sarà una (1/k) possibilità che il ciclo terminerà, perché abbiamo bisogno di due 1 per che ciò accada e la possibilità che ogni voce sia 1 è 1/k. Il numero di iterazioni prima di terminare seguirà un Geometric distribution dove p è (1/k) e il numero previsto di "prove" (iterazioni) prima del "successo" (interruzione del ciclo) non dipende da n (eccetto come limite superiore per il numero di prove) in modo che il ciclo più interno funzioni in tempo costante (in media) per un dato k, rendendo l'algoritmo complessivo O (n). La formula di distribuzione geometrica dovrebbe darti un'idea di cosa succede se k = n. Si noti che nella formula fornita su Wikipedia k è il numero di prove.