Алгоритм умножения булевых матриц

Question

Это мой первый вопрос по stackru. Я решал некоторые упражнения из "Алгоритм проектирования" Гудрича, Тамассия. Тем не менее, я совершенно не в курсе этой проблемы. 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;
    }
}

Для булевой матрицы, как указано в задаче, вместо умножения используется AND, а вместо сложения OR, так что получается:

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

Здесь следует обратить внимание на то, что, как только наша логическая "сумма" будет истинной, мы можем прекратить вычисление и выйти из самого внутреннего цикла, потому что OR, если любые последующие значения с истинным значением приведут к истинному значению, поэтому мы можем сразу узнать, что конечный результат будет правдой.

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