Unidade 1 Analise de Algoritmos - Ronie Camilo - UAM

Prévia do material em texto

Contextualização 
Caro(a) aluno(a), 
O comportamento assintótico de funções apresentado nesta unidade é uma 
poderosa técnica empregada na comparação da eficiência entre algoritmos. 
Análises desse tipo são fundamentais para que a inserção de um novo 
procedimento computacional em um sistema já existente não comprometa o seu 
desempenho geral. 
Considere que um sistema responsável por executar várias operações 
matemáticas precisa ser atualizado. Até o momento, uma das principais 
operações executadas é a soma de matrizes, cujo algoritmo é descrito a seguir. 
 
Algoritmo SomaMatriz 
Entrada: duas matrizes A e B quadradas de tamanho n 
Saída: matriz C correspondente à soma das matrizes A e B 
1. para i = 1 até n faça 
2. para j = 1 até n faça 
3. C[ i, j ] = A[ i, j ] + B[ i, j ] 
4. fim para 
5. fim para 
6. retorna C 
Um novo procedimento de multiplicação de matrizes precisa ser introduzido no 
sistema. O algoritmo que executa essa operação é descrito a seguir. 
Algoritmo MultiplicaMatriz 
Entrada: duas matrizes A e B quadradas de tamanho n 
Saída: Matriz C correspondente ao produto das matrizes A e B 
1. para i = 1 até n faça 
2. para j = 1 até n faça 
3. para k = 1 até n faça 
3. C[ i, j ] = C[ i, j ] + A[ i, k ] x B[ k, j ] 
4. fim para 
4. fim para 
5. fim para 
6. retorna C 
 
Proposta 
Considerando o cenário apresentado: 
 
Explique se a eficiência do sistema permanecerá a mesma ou se sofrerá alguma 
alteração com a introdução do novo procedimento de multiplicação de matrizes. 
Fundamente sua explicação apresentando um comparativo das complexidades 
dos dois algoritmos. 
 
Resposta: 
 
 Os passos para execução do primeiro algoritmo SomaMatriz seria 2 
linhas x colunas + 2 linhas + 1 = O(n2) sua complexidade assintótica encontrada 
foi Ɵ (linhas x Colunas) de nome quadrática com itens processados aos pares 
comumente aninhados. 
Já no segundo algoritmo MultiplicaMatriz usa a complexidade Assintótica 
de forma O(n3) de nome cúbica, apenas para ler e escrever são necessárias n2 
operações, sendo assim, ambas cotas inferiores dos dois algoritmos seria Ω(n2) 
e não alteraria a eficiência do sistema. 
 
Referências: Sites de pesquisa na internet e Materiais de estudo UAM.