[C] Determinante de orden N

A partir del título de este post ( http://foro.elhacker.net/programacion_cc/determinante_matriz_de_orden_n-t352910.0.html ) me entró la curiosidad de resolverlo de manera dinámica. Y la manera que se me ocurría para un algoritmo sencillo pues es la regla de Laplace o el desarrollo por menores complementarios de manera recursiva:

Código

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define N 4
 
/* DETERMINANTE DE UNA MATRIZ de orden N - por MAFH */
 
typedef int ** matriz;
 
void visualizar_matriz (matriz matrix, int m, int n) {
    int i,j;
    for (i=0; i<m; i++) {
        for(j=0; j<n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}
 
matriz generar_matriz (int m, int n) {
    int i;
    matriz temp;
    if ((temp = (matriz) malloc(m*sizeof(int*))) == NULL)
        return NULL;
    for (i=0; i<m; i++)
        if ((temp[i] = (int *)malloc(n*sizeof(int))) == NULL)
            return NULL;
    return temp;
}
 
matriz copiar_matriz (matriz matrix, int m, int n) {
    int i,j;
    matriz temp = (matriz) generar_matriz(m,n);
    if (temp != NULL) {
		for (i=0; i<m; i++)
			for (j=0; j<n; j++)
				temp[i][j] = matrix[i][j];
    }
    return temp;
}
 
void liberar_matriz (matriz matrix, int m) {
    int i;
    for (i=0; i<m; i++)
        free(matrix[i]);
    free(matrix);
}
 
void rellenar_matriz (matriz matrix, int m, int n) {
    int i,j;
    for (i=0; i<m; i++)
        for(j=0; j<n; j++) {
            printf("Valor de matrix[%d,%d] = ", i, j);
            scanf("%d", &(matrix[i][j]));
        }
}
 
matriz adjunto_matriz (matriz matrix, int fila, int columna, int n) {
    matriz adjunto = (matriz) generar_matriz(n-1,n-1);
    if (adjunto != NULL) {
		int i, j, k=0, l=0;
		for (i=0; i<n; i++)
			for (j=0; j<n; j++) {
				if ((i != fila) && (j != columna)) {
					adjunto[k][l] = matrix[i][j];
					if (++l == n-1) {
						l=0;
						k++;
					}
				}
			}
    }
    return adjunto;
}
 
int determinante (matriz matrix, int n) {
    if (n == 1) {
        return matrix[0][0];
    } else {
        int j;
        int res = 0;
        for (j=0; j<n; j++){
            matriz adjunto = (matriz) adjunto_matriz(matrix, 0, j, n);
            if (adjunto == NULL) exit(1);
            res += pow(-1, (j%2))*matrix[0][j]*determinante(adjunto, n-1);
            liberar_matriz(adjunto,n-1);
        }
        return res;
    }
}
 
 
int main (int argc, char ** argv) {
    matriz m = (matriz) generar_matriz(N,N);
    rellenar_matriz(m,N,N);
    visualizar_matriz(m,N,N);
    printf("|M| = %d\n", determinante(m,N));
    liberar_matriz(m,N);
    return 0;
}

Aunque tenemos la constante N para el orden de la matriz, podemos utilizar una variable para que el usuario introduzca el orden, evidentemente.

Una ejecución del código con Valgrind:

Citar

pyxolo@ubuntu:~/Escritorio$ gcc -o det determinanteN.c -lm
pyxolo@ubuntu:~/Escritorio$ valgrind ./det -all
==4938== Memcheck, a memory error detector
==4938== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==4938== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==4938== Command: ./det -all
==4938==
Valor de matrix[0,0] = 2
Valor de matrix[0,1] = 3
Valor de matrix[0,2] = -4
Valor de matrix[0,3] = 2
Valor de matrix[1,0] = 9
Valor de matrix[1,1] = 11
Valor de matrix[1,2] = 0
Valor de matrix[1,3] = 3
Valor de matrix[2,0] = 2
Valor de matrix[2,1] = -4
Valor de matrix[2,2] = -5
Valor de matrix[2,3] = -6
Valor de matrix[3,0] = 21
Valor de matrix[3,1] = 100
Valor de matrix[3,2] = 2
Valor de matrix[3,3] = 3
2 3 -4 2
9 11 0 3
2 -4 -5 -6
21 100 2 3
|M| = -23240
==4938==
==4938== HEAP SUMMARY:
==4938== in use at exit: 0 bytes in 0 blocks
==4938== total heap usage: 105 allocs, 105 frees, 752 bytes allocated
==4938==
==4938== All heap blocks were freed -- no leaks are possible
==4938==
==4938== For counts of detected and suppressed errors, rerun with: -v
==4938== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Conclusión del desarrollo por menores:

Orden 1:
1 de orden 1
no llamadas recursivas

Orden 2:
2 de orden 1
2 = 2 llamadas recursivas

Orden 3:
3 de orden 2
2 de orden 1
3*2 = 6 llamadas recursivas

Orden 4:
4 de orden 3
3 de orden 2
2 de orden 1
4*3*2 = 24 llamadas recursivas

Orden 5:
5 de orden 4
4 de orden 3
3 de orden 2
2 de orden 1
5*4*3*2 = 120 llamadas recursivas

Orden n:
n de orden n-1
n-1 de orden n-2
.... de orden ...
3 de orden 2
2 de orden 1
n*(n-1)*(n-2)*(n-3)*...*(n-n+1) = (productorio desde i=n hasta 2 de i) = n! llamadas recursivas

Como conclusión a los resultados expuestos obtenemos que el número de llamadas recursivas que se realizan viene dado por:

Nº llamadas recursivas = Permutaciones(Orden) = Orden!

Como bien había dicho ghastlyX en respuesta al tema arriba enlazado.

Edit:

He tratado de lanzar el código con un determinante de orden 13 y evidentemente "no terminaba"...
Nº llamadas recursivas = P(13) = 13! = 6227020800

T(n) es exponencial y encima con los alojos y desalojos de memoria... Para morirse xD

Por otra parte, convendría generar los adjuntos con la misma matriz que se usa o de alguna manera sin generar otra matriz de tamaño n-1 para cada adjunto ._.