• Author / Uploaded
• Miguel Angel Cubillos Fajardo

Citation preview

Complejidad algoritmo determinante El algoritmo utiliza el método de cofactores para calcular el determinante. Para correr el programa, el usuario debe ingresar primeramente el tamaño de la matriz cuadrada, el cual es un valor que debe ser positivo y menor a 15, aunque se recomienda que sea menor a 10 para mayor velocidad de procesamiento, además, el usuario debe ingresar componente a componente los valores de la matriz; el programa le indica el valor de la fila y columna en el que el usuario está ingresando el valor. El programa usa tres funciones, una para imprimir los valores de la función, otra para calcular el determinante y otra para calcular el cofactor de una posición de la matriz, las últimas 2 funciones se hacen llamadas entre ellas.

COMPLEJIDAD La complejidad se basa en la complejidad de las dos funciones recursivas, se empieza con la función determinante la cual llama a la función cofactor, y esta a su vez llama a la función determinante, pero disminuyendo el tamaño de entrada. Un árbol para el caso en el que el usuario ingresa el tamaño n = 3 es: Det (n=3)

Cof (n=3)

Cof (n=3)

© Universidad Internacional de La Rioja (UNIR)

Det (n=2)

Cof (n=3)

Det (n=2)

Det (n=2)

Cof (n=2)

Cof (n=2)

Cof (n=2)

Cof (n=2)

Cof (n=2)

Cof (n=2)

Det (n=1)

Det (n=1)

Det (n=1)

Det (n=1)

Det (n=1)

Det (n=1)

1

Según lo observado en el árbol del diagrama anterior se puede establecer la siguiente serie de número de hojas de cada nivel como: 1, 3, 3, 6, 6. La anterior serie escrita en términos de la letra n es: 1, n, n, n*(n-1), n*(n-1). Al unir los niveles de los cofactores con el nivel de cofactor siguiente, se tiene la serie: 1, 2n, 2*n*(n-1). Con el análisis del ejemplo anterior se puede establecer la serie del número de hojas de cada uno de los niveles del árbol, desde el nivel más bajo del árbol al nivel más superior del mismo de la siguiente manera: T(n) = 2*n*T(n-1) T(n-1) = 2* (n-1) * T(n-2) T(n-2) = 2* (n-2) * T(n-3) T(n-3) = 2* (n-3) * T(n-4) … T(n-(n-1))=T(1)=1

Así que el término T(n) de la expresión se puede reescribir en término de los anteriores términos de la siguiente manera: T(n) = 2n*2(n-1)*2(n-2)*2(n-3)*…*1 De esta manera se puede factorizar el 2 de todos los términos de la siguiente manera: T(n) = 2* (n*(n-1)*(n-2)*(n-3)*…*1/2 ) < 2* (n*(n-1)*(n-2)*(n-3)*…*1 ) = 2* n! De esta manera la función O grande del algoritmo del cálculo del determinante es: O(n!) pues el 2 es una constante y la función O grande no tiene en cuenta esos valores

© Universidad Internacional de La Rioja (UNIR)

constantes.

2