Complexidade Algorítmica do Teorema de Laplace no Cálculo de Determinantes

Por
|  

Antes de começar, é importante alertar o leitor que este não é um artigo com o intuito de ensinar o teorema de Laplace. Aqui, faço uma análise do teorema do ponto de vista computacional. Caso você precise de um artigo para aprender o teorema, procure outra fonte.

Introdução

O teorema de Laplace (Laplace Expansion, em inglês) permite calcular o determinante de matrizes de qualquer ordem através de uma expansão em cofatores. Na prática, o cálculo do determinante é realizado calculando-se os determinantes de matrizes de ordem inferior. Por exemplo, o determinante de uma matriz de ordem cinco é calculado a partir dos determinantes de cinco matrizes de ordem quatro.

O intuito deste texto é analisar a complexidade do teorema na resolução de determinantes. Tal análise faz uso de conceitos um tanto avançados de Cálculo Diferencial, portanto é importante ter noções de Cálculo para compreender o artigo.

Inicialmente, é feita uma rápida revisão sobre o teorema com o intuito de compreendê-lo. Depois, faço uma análise das chamadas recursivas necessárias para computar um determinante através do teorema. Em seguida, apresento a equação de recorrência do algoritmo e resolvo-a considerando dois casos distintos. Por fim, realizo algumas observações finais.

Comentários 0