3.3. Ejemplos de aplicación.
Supongamos que representamos números enteros (de tamaño arbitrariamente grande) mediante listas de cifras.
EnteroLargo = pointer to nodo;
Con el algoritmo clásico de multiplicación, multiplicamos todos los dígitos de un entero por los del otro y sumamos (con los desplazamien-tos adecuados).
El algoritmo tendrá un orden de O(n·m), suponiendo n y m las longitudes de los enteros. Si las suponemos iguales, entonces O(n2).
Podemos aplicar la técnica divide y vencerás:
- Divide: los enteros de tamaño n son divididos en tamaño n/2.
- Solucionar los subproblemas de tamaño n/2.
- Combinar: sumar los resultados de los anteriores (con los desplazamientos adecuados).
3.3.1. Multiplicación rápida de enteros largos.