Análises de Algoritímos - Atividade 01

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 a os 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.