Algorytm mnożenia macierzy Boole'a

Question

To jest moje pierwsze pytanie na stackoverflow. Rozwiązałem kilka ćwiczeń z projektu "Algorithm" Goodricha, Tamassii. Jednak nie mam pojęcia o tym problemie. Unusre od czego zacząć i jak postępować. Każda rada byłaby świetna. Oto problem:

Macierzach logicznych są macierze takie, że każdy wpis jest równy 0 lub 1, a mnożenie macierzy wykonywane jest za pomocą AND dla * i OR dla +. Załóżmy, że otrzymujemy dwie losowe macierze Bo i A N, NxN, tak że prawdopodobieństwo, że dowolny wpis w którymkolwiek z nich wynosi 1, wynosi 1/k. Pokaż, że jeśli k jest stałą, to istnieje algorytm dla mnożenia A i B, których oczekiwany czas działania to O (n^2). Co jeśli k jest n?

Answer 1

Mnożenie macierzy przy użyciu standardowego podejścia iteracyjnego to O (n), ponieważ trzeba wykonać iterację po n wierszach i n kolumnach, a dla każdego elementu wykonać wektor mnożąc jeden z wierszy i jedną z kolumn , która przyjmuje n mnożeń i n-1 dodatków.

kod Psuedo do mnożenia macierzy przez macierzy B i przechowywać w macierzy 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; 
    } 
} 

przypadku logicznej matrycy, jak określono w problemu, i jest stosowany w miejsce mnożenie i lub w miejscu Ponadto, dzięki czemu staje się to:

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; 
    } 
} 

rzeczą godną uwagi jest to, że gdy nasza logiczna „suma” jest prawdziwe, możemy zatrzymać obliczanie i wcześnie z najbardziej wewnętrznej pętli, ponieważ Oring żadnych kolejnych wartości z TRU e będzie produkować prawdziwe, więc możemy od razu wiedzieć, że ostateczny wynik będzie prawdziwy.

Dla każdej stałej k, liczba operacji, zanim będziemy mogli to zrobić wcześnie (zakładając, że wartości są losowe) będzie zależeć od k i nie wzrośnie za pomocą n. Przy każdej iteracji będzie szansa, że ​​pętla się zakończy, ponieważ potrzebujemy dwóch 1s, aby to się stało, a szansa na to, że każda pozycja jest równa 1 to 1/k. Liczba iteracji przed zakończeniem będzie następować po Geometric distribution, gdzie p jest (1/k) , a spodziewana liczba "prób" (iteracji) przed "sukcesem" (wyjściem z pętli) nie zależy od n (z wyjątkiem górnego ograniczenia dla liczby prób), tak że najgłębsza pętla działa w stałym czasie (średnio) dla danego k, tworząc ogólny algorytm O (n). Formuła rozkładu geometrycznego powinna dać ci pewien wgląd w to, co się dzieje, gdy k = n. Zauważ, że we wzorze podanym na Wikipedii k jest liczbą prób.