Page 46 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Para una matriz de 4x4, en la primera etapa recursiva en profundidad se requieren cuatro llamadas
recursivas con matrices de 3x3. En la segunda etapa, cada matriz de 3x3 requiere tres llamadas
recursivas con matrices de 2x2. Siendo un criterio de paro, el cálculo de matrices de 2x2 con un
costo de una unidad. Para una matriz de NxN, la primer etapa en profundidad tendrá N llamadas con
matrices de tamaño (N-1)x(N-1); en la segunda llamada en profundidad, cada matriz de tamaño (N-1)
x(N-1) tendrá N-1 llamadas con matrices de tamaño (N-2)x(N-2), obteniéndose un orden de llamadas
factorial (ver figura 1.8). Por eso, una matriz de tamaño NxN tendrá una complejidad (N!), siendo
N el número de hileras.

Figura 1.8. Árbol recursivo del cálculo del determinante de una matriz de 4x4

Opción B: Por el método de Gauss

Un método iterativo para calcular el determinante es el de Gauss, cuyo principio básico es el si-
guiente: uno puede cambiar una representación matricial A del conjunto original por una nueva, pero
equivalente representación matricial según las siguientes reglas:

• Se puede multiplicar una hilera por una constante y la matriz es equivalente.

• Se podrá permutar una hilera por otra y el sistema es equivalente. Para el caso
del cálculo del determinante, cada vez que se tenga una permutación existirá un
cambio de signo al resultado. Por ejemplo, si existieron permutaciones impares, el
resultado del cálculo del determinante se multiplicará por menos uno.

40