TL; versión DR
El método ingenuo tiene tres bucles, cada bucle ejecuta N veces (de 0 a N – 1). Entonces, la complejidad del tiempo será [matemática] O (N ^ 3) [/ matemática] de los tres bucles en sí, y el costo de la asignación, suma, operaciones de multiplicación, etc. será [matemática] c * N ^ 3 [/ math] para algunos [math] c [/ math] (para las operaciones dentro del bucle k más interno) o estará dominado por el término [math] c * N ^ 3 [/ math].
Puede estimar la complejidad temporal de un algoritmo con una precisión razonable a un alto nivel desde el programa / pseudocódigo mismo. Este enfoque es simple para algoritmos iterativos. Los algoritmos recursivos deben ser atacados formulando relaciones de recurrencia (como ya ha visto).
La larga respuesta
1) Estimación de la complejidad del tiempo (paso a paso) del método iterativo.
El procedimiento general
Para algoritmos iterativos, primero necesita estimar aproximadamente cuántas instrucciones necesitará cada paso o declaración del algoritmo (pseudocódigo / programa) (para una ejecución de ese paso). Esto se puede llamar el recuento de instrucciones . Puede suponer a un alto nivel que la suma, la multiplicación, la operación de asignación, las llamadas a funciones, etc. se pueden hacer en una sola instrucción (aunque en realidad, esto puede no ser siempre el caso, como cuando se opera en enteros grandes). Si un paso contiene una llamada de función, debe contar tanto la instrucción de llamada de función como la complejidad de tiempo de la función llamada, que se puede obtener haciendo este mismo proceso en esa función. A menos que sea una función predefinida como printf() , en cuyo caso, en el mejor de los casos, puede asumir una complejidad de tiempo constante.
- ¿El determinante se define arbitrariamente solo para encontrar la singularidad de la matriz?
- ¿Cuál es la relación entre el aprendizaje automático y la optimización matemática?
- ¿Cuál es el significado de la forma normal de Smith?
- ¿Qué es una explicación intuitiva del rango de una matriz?
- ¿Cuál es la intuición matemática detrás del determinante de una matriz? ¿Cómo se concibió su definición y por qué es importante? ¿Qué significa intuitivamente?
Luego asigne una frecuencia a cada declaración (que denota el número de veces que se ejecutará esa declaración). La frecuencia de ejecución de algunas declaraciones deberá expresarse en términos de tamaño de entrada. Por ejemplo, en un algoritmo de búsqueda secuencial, el paso de comparación se realizará [matemática] N [/ matemática] veces, donde [matemática] N [/ matemática] es el número de elementos en la matriz / lista.
Después de calcular las frecuencias, multiplica el recuento de instrucciones para cada instrucción con su frecuencia para ver cuántas instrucciones se ejecutarán para esa instrucción en total, durante una ejecución del algoritmo. Y finalmente, sume todos los productos para obtener una estimación de cuántas instrucciones requerirá una ejecución del algoritmo.
El resultado de la suma será una función de [matemática] N [/ matemática] ya que las frecuencias de cada paso dependerán típicamente del tamaño de entrada [matemática] N [/ matemática].
Luego, puede expresar la función obtenida por suma en notación asintótica (gran Oh, gran Theta, gran Omega, etc.) para obtener una expresión más sucinta.
Analizando el primer algoritmo (método ingenuo)
Ahora, para encontrar la complejidad temporal del primer algoritmo
multiplicación nula (int A [] [N], int B [] [N], int C [] [N]) {
Paso 1 : para (int i = 0; i <N; i ++) {
Paso 2 : para (int j = 0; j <N; j ++) {
Paso 3 : C [i] [j] = 0;
Paso 4 : para (int k = 0; k <N; k ++) {
Paso 5 : C [i] [j] + = A [i] [k] * B [k] [j];
}
}
}
}
Para el paso 1, se ejecutará una instrucción for loop, [math] 2 [/ math] (comparar e incrementar) para cada iteración del loop, y la instrucción [math] 1 [/ math] (la inicialización de i ) ejecutarse una vez antes de ingresar al bucle.
El bucle del paso 1 obviamente se ejecutará [matemática] N [/ matemática] veces. Entonces, multiplicando [matemáticas] 2 [/ matemáticas] por [matemáticas] N [/ matemáticas] y sumando las [matemáticas] 1 [/ matemáticas] adicionales (que no deben multiplicarse por [matemáticas] N [/ matemáticas]) da un total de instrucciones [matemáticas] 2N + 1 [/ matemáticas] del Paso 1 mismo.
El paso 2 puede analizarse de manera similar. El ciclo se ejecutará un total de [matemática] N ^ 2 [/ matemática] veces (porque el ciclo del Paso 2 se ejecutará [matemática] N [/ matemática] veces para cada iteración del ciclo del Paso 1, y habrá [matemática] N [/ matemática] tales iteraciones). Entonces, obtenemos un total de [matemáticas] 2N ^ 2 + 1 [/ matemáticas] del paso 2.
Para el paso 3 , se ejecutará una sola instrucción una vez para cada iteración del bucle del paso 2, es decir, [matemática] N ^ 2 [/ matemática] veces. Entonces, un total de [matemáticas] 1 * N ^ 2 [/ matemáticas] instrucciones del Paso 3.
El paso 4 es otro ciclo. Se ejecutará [matemática] N [/ matemática] veces para cada iteración del bucle del paso 2, es decir, se ejecutará [matemática] N ^ 2 * N = N ^ 3 [/ matemática] veces. Entonces, un total de [matemáticas] 2N ^ 3 + 1 [/ matemáticas] instrucciones del paso 4.
El paso 5 es una expresión que involucra 2 multiplicaciones, 1 suma y 1 asignación. Entonces, [matemáticas] 4 [/ matemáticas] instrucciones para cada iteración, y habrá iteraciones [matemáticas] N ^ 3 [/ matemáticas], entonces un total de instrucciones [matemáticas] 4N ^ 3 [/ matemáticas] del paso 5.
Para calcular el total total, sumamos todos estos productos. Entonces,
[matemática] T (n) = 2N + 1 + 2N ^ 2 + 1 [/ matemática] [matemática] + N ^ 2 + 2N ^ 3 + 1 + 4N ^ 3 [/ matemática]
[matemáticas] = 6N ^ 3 + 3N ^ 2 + 2N + 3 [/ matemáticas]
Luego aplique la notación Oh grande para encontrar (trivialmente) que T (n) es [matemática] O (N ^ 3) [/ matemática].
Segunda parte de la pregunta
El código para la solución divide y vencerás será completamente diferente de la implementación ingenua. El pseudocódigo será algo así como
DandC-Matrix-Multiply (M1, M2)
A: = nueva matriz desde la parte superior izquierda de M1
B: = nueva matriz desde la parte superior derecha de M1
C: = nueva matriz desde la parte inferior izquierda de M1
……………………… ..
E: = nueva matriz desde la parte superior izquierda de M2
……………………… ..
H: = nueva matriz desde la parte inferior derecha de M2
P: = Matrix-Add (DandC-Matrix-Multiply (A, E),
DandC-Matrix-Multiply (B, G))
Q: = Matrix-Add (DandC-Matrix-Multiply (A, F),
DandC-Matrix-Multiply (B, H))
R: = Matrix-Add (DandC-Matrix-Multiply (C, E),
DandC-Matrix-Multiply (D, G))
S: = Matrix-Add (DandC-Matrix-Multiply (C, F),
DandC-Matrix-Multiply (D, H))
Combina P, Q, R y S en una única matriz M3
Devolver M3
Nota: Crear nuevas matrices A, B, …, P, Q, R, S, etc. (lo que implicará muchas copias de elementos). puede evitarse utilizando desplazamientos de índice para pasar las DandC-Matrix-Multiply() A, B, …, G, H a DandC-Matrix-Multiply() y almacenando las matrices intermedias P, Q, R, S en las regiones correctas de M3 en su lugar de devolver nuevas matrices.
Este algoritmo básico de multiplicación de bloques dividir y conquistar se deriva de la definición de la multiplicación de matrices en sí. El algoritmo de Strassen (mencionado en la pregunta), por otro lado, utiliza descomposiciones matemáticas no obvias (en mi opinión, al menos) para reducir la complejidad asintótica a [matemáticas] O (n ^ {lg 7}) [/ matemáticas ] de [math] O (n ^ 3) [/ math], pero trae consigo su propio conjunto de problemas (como constantes más grandes ocultas por notación asintótica, inestabilidad numérica, etc.).