Thuật toán nhân ma trận Boolean

Question

Đây là câu hỏi đầu tiên của tôi về lưu lượng truy cập stackoverflow. Tôi đã giải quyết một số bài tập từ "Thiết kế thuật toán" của Goodrich, Tamassia. Tuy nhiên, tôi hoàn toàn không biết gì về vấn đề này. Unusre bắt đầu từ đâu và cách tiến hành. Bất cứ lời khuyên nào cũng tuyệt vời cả. Đây là vấn đề:

Ma trận Boolean là ma trận sao cho mỗi mục nhập là 0 hoặc 1 và phép nhân ma trận được thực hiện bằng cách sử dụng AND cho * và OR cho +. Giả sử chúng ta có hai ma trận Boolean Boolean ngẫu nhiên A và B, sao cho xác suất mà bất kỳ mục nhập nào trong cả hai là 1, là 1/k. Cho thấy rằng nếu k là hằng số, thì có một thuật toán nhân A và B với thời gian chạy dự kiến ​​là O (n^2). Nếu k là n thì sao?

Answer 1

Nhân ma trận bằng cách sử dụng phương pháp lặp chuẩn là O (n), vì bạn phải lặp qua n hàng và n cột và cho mỗi phần tử thực hiện nhân vectơ của một trong các hàng và một trong các cột , có n nhân và n-1 bổ sung.

mã giả để nhân ma trận một bởi ma trận b và lưu trữ trong ma trận 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; 
    } 
} 

Đối với một ma trận boolean, như quy định trong vấn đề này, và được sử dụng trong nơi nhân và OR ở vị trí của Ngoài ra, vì vậy nó trở thành này:

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

những điều cần chú ý ở đây là một khi boolean của chúng tôi "tổng" là đúng, chúng ta có thể dừng việc tính toán và đầu ra khỏi vòng lặp trong cùng, vì ORing bất kỳ giá trị tiếp theo với trù e sẽ tạo ra sự thật, vì vậy chúng ta có thể biết ngay rằng kết quả cuối cùng sẽ đúng.

Đối với bất kỳ hằng số k, số hoạt động trước khi chúng tôi có thể thực hiện việc này sớm (giả sử các giá trị là ngẫu nhiên) sẽ phụ thuộc vào k và sẽ không tăng với n. Tại mỗi lần lặp lại sẽ có cơ hội (1/k) rằng vòng lặp sẽ kết thúc, bởi vì chúng ta cần hai giây cho điều đó xảy ra và cơ hội của mỗi mục nhập là 1 là 1/k. Số lần lặp lại trước khi kết thúc sẽ theo sau Geometric distribution trong đó p là (1/k) và số lượng "thử nghiệm" (lần lặp) dự kiến ​​trước khi "thành công" (vi phạm vòng lặp) không phụ thuộc vào n (ngoại trừ một giới hạn trên cho số lần thử nghiệm) để vòng lặp bên trong nhất định chạy trong thời gian không đổi (trung bình) cho một k cho trước, làm cho thuật toán tổng thể O (n). Công thức phân bố hình học sẽ cung cấp cho bạn một số thông tin chi tiết về những gì sẽ xảy ra nếu k = n. Lưu ý rằng trong công thức được đưa ra trên Wikipedia k là số lần thử nghiệm.