Quiero multiplicar estas dos matrices. Después reduzco cualquier matriz anidada con el producto de sus valores.
[ [ 1 ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] [ [ 2, 3, 4 ], [ 3, 4 ], [ 4 ], [ 1 ] ]La respuesta debería ser:
[24, 12, 8, 6]Aclaración:
24 = 1 * 2 * 3 * 4
Si hay algún otro enfoque, por favor hágamelo saber. El código no puede ser superior a O(n) y no puede utilizarse el operador de división .
Cuando se habla de una big-o complejidad como O(n) , es importante saber a qué se refiere la n . En el caso de una matriz simple, normalmente es el tamaño de la matriz. Sin embargo, en su caso, tiene matrices de matrices, por lo que n puede referirse al tamaño de la matriz interna o externa.
Para simplificarlo, considere que el arreglo exterior contiene x arreglos y los arreglos internos tienen y elementos. Luego requiere multiplicaciones 2y-1 para cada matriz interna. Dado que hay x arreglos internos, en total requerirá x(2y-1) multiplicaciones. En big-o sería O(xy).
Entonces, para responder a tu pregunta.
Si su n se refiere al número de arreglos internos o al número de elementos en los arreglos internos, entonces sí, será O(n).
Sin embargo, si su n se refiere tanto a la dimensión interna como a la externa (es decir, ambas crecen al mismo tiempo), entonces no, será O(n^2).
En forma de tabla:
-------------------------------------------------- | Outer dimension | Inner dimension | Complexity | -------------------------------------------------- | growing | constant | O(n) | -------------------------------------------------- | constant | growing | O(n) | -------------------------------------------------- | growing | growing | O(n^2) | --------------------------------------------------Y solo para aclarar: no hay magia que pueda convertir el último caso en O(n).