Логический алгоритм умножения матрицы

Question

Это мой первый вопрос о stackoverflow. Я решал некоторые упражнения из «Алгоритм-дизайна» Гудрича, Тамасия. Однако я совершенно не знаю об этой проблеме. Unusre, с чего начать и как действовать. Будем признательны любому совету. Вот проблема:

Булевы матрицы - это такие матрицы, что каждая запись равна 0 или 1, а матричное умножение выполняется с использованием AND для * и OR для +. Предположим, нам даны две NxN случайные булевы матрицы A и B, так что вероятность того, что любая запись равна 1, равна 1/k. Покажите, что если k - константа, то существует алгоритм умножения A и B, ожидаемое время работы которого O (n^2). Что, если k - n?

Answer 1

Матричное умножение с использованием стандартного итерационного подхода - это O (n), так как вы должны выполнять итерацию по n строкам и n столбцам, а для каждого элемента вектор умножается на одну из строк и один из столбцов , который принимает n умножений и n-1 дополнений.

псевдопользователей код для умножения матрицы А матрицы Ь и хранить в матрице с:

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

Для булевой матрицы, как указано в задаче, и используется в вместо умножения и ИЛИ вместо Кроме того, так что становится это:

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

Дела заметить здесь в том, что когда-то наша булевой «сумма», правда, мы можем остановить вычисления и рано из внутреннего цикла, так как ORing любых последующих значений с Tru e будет выдавать истину, поэтому мы сразу можем знать, что окончательный результат будет правдой.

Для любой константы k количество операций, прежде чем мы сможем сделать это раньше (при условии, что значения являются случайными), будет зависеть от k и не будет увеличиваться с n. На каждой итерации будет (1/k) вероятность того, что цикл завершится, потому что нам нужно два 1s для этого, и вероятность того, что каждая запись будет равна 1, равна 1/k. Число итераций до завершения будет следовать за Geometric distribution, где p является (1/k) , а ожидаемое количество «проб» (итераций) до «успеха» (выход из цикла) не зависит от n (кроме как верхняя граница для количества испытаний), поэтому самый внутренний цикл работает в постоянное время (в среднем) для заданного k, делая общий алгоритм O (n). Формула геометрического распределения должна дать вам некоторое представление о том, что произойдет, если k = n. Заметим, что в формуле, приведенной в Википедии, k - количество испытаний.