Размер подзадачи по алгоритму умножения матриц Штрассена

Недавно я смотрел видеолекцию о рекурсивном алгоритме Штрассена для умножения матриц размера 2 n x n. В лекции также был рассмотрен мастер-метод для вычисления временной сложности этого алгоритма. Однако при обсуждении коэффициента b, который, насколько я понимаю, относится к коэффициенту уменьшения размера подзадач, ему было присвоено значение 2.

Мой вопрос: поскольку матрицы 2 n x n рекурсивно делятся на матрицы 8 n/2 x n/2, почему значение b равно 2, а не 4?

Заранее спасибо!


recursion algorithm matrix-multiplication master-theorem strassen
person Brandon Thio    schedule 02.02.2021    source источник

Ответы (1)


arrow_upward
0
arrow_downward

n в обозначении сложности O(n3) совпадает с n в n×n, поэтому сложность выражается как функция размера одного измерения матриц. Поскольку при каждой рекурсии это значение уменьшается вдвое, b равно 2.

Вы можете видеть, что наивный алгоритм действительно проходит через три вложенных цикла размером n (длина одной строки/столбца), а не n×n (размер всего матрица), так что это кажется правильным.

person Svante    schedule 02.02.2021