Análise de Algoritmos - A1

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. 
Submeta o arquivo de sua resposta para avaliação docente.
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.