Re: [obm-l] Cramer vs Eliminacao

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Wed, May 26, 2004 at 03:44:34PM -0300, Claudio Buffara wrote:
> Oi, pessoal:
> 
> Multiplicaoes e divisoes sao operacoes muito mais demoradas numa CPU do que
> somas e subtracoes. Assim, para se determinar a eficiencia de um dado
> algoritmo, eh usual que se estime apenas o numero de multiplicaoes e/ou
> divisoes que ele requer.
> 
> Pra ter uma ideia do quanto a regra de Cramer eh ineficiente pra se resolver
> sistemas lineares, calcule o seguinte:
> 
> 1) Quantas multiplicacoes e/ou divisoes sao necessarias para se resolver um
> sistema linear n x n (suposto consistente)?
> 
> 2) Qual o numero maximo de multiplicacoes e/ou divisoes necessarias para se
> resolver o mesmo sistema via eliminacao gaussiana (escalonamento)?

É difícil fazer esta comparação direito se não soubermos qual algoritmo
vai ser usado para calcular os determinantes na fórmula de Cramer.
Uma boa maneira de calcular determinantes é justamente fazer
eliminação gaussiana na matriz, e neste caso Cramer fica sendo
quase exatamente n vezes mais lento do que usar diretamente
eliminação gaussiana no sistema.

Existem algoritmos mais lentos para calcular o determinante
(por exemplo: olhar para todas as permutações ou expandir
recursivamente por linhas ou colunas) mas eu não acho que
seja justo medir a eficiência de Cramer usando um algoritmo ineficiente
para calcular o determinante.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================