Algoritmo de Strassen para el análisis de complejidad de multiplicación de matrices

8

Veo en todas partes que la ecuación recursiva para la complejidad de Strassen alg es: Esto no está tan claro para mí. Se supone que el parámetro es el tamaño de la entrada, pero parece que aquí es una dimensión de una matriz, mientras que el tamaño de entrada es en realidad . Además, cada matriz de la entrada se divide en 4 submatrices, por lo que parece que la ecuación recursiva debería ser

T(norte)=7 7T(norte2)+O(norte2).
nortenorte2
T(norte)=7 7T(norte4 4)+O(norte).

dafnahaktana
fuente

Respuestas:

13

Es cierto que el parámetro nortegeneralmente denota el tamaño de la entrada, pero este no es siempre el caso. Para la multiplicación de matriz cuadrada,nortedenota el número de filas (o columnas). Para gráficos,norte a menudo denota el número de vértices, y metroEl número de aristas. Para algoritmos sobre funciones booleanas,norte denota el número de entradas, aunque la tabla de verdad en sí tiene tamaño 2norte. Hay muchos otros ejemplos.

Yuval Filmus
fuente
5

Vuelve al tamaño de la matriz. Supongamos que la matriz original esnorte×norte. Por lo tanto, consideraremosT(norte) como un cálculo de dos matrices con tamaño de norte×norte. Cuando dividimos la matriz original en 4 partes, el tamaño de cada parte esnorte2×norte2. Por lo tanto, el costo de cálculo de la multiplicación de dos matrices con este tamaño esT(norte2).

Dios mio
fuente
0

La complejidad del tiempo a menudo se basa en el tamaño de entrada, pero no es un requisito absoluto. En este caso, para la multiplicación de matrices nxn, parece más natural contar la cantidad de operaciones basadas en n, no en el tamaño del problema nx n.

gnasher729
fuente