Atividade 01

Prévia do material em texto

Multiplicação de Matriz 
 Am × n × Bn × p = Cm × 
 
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 
 
 
O algoritmo tem complexidade no tempo O (m x p x n) ou O(n^3), se as matrizes 
forem quadradas de ordem n. Possui um tempo de execução cúbico. 
O produto m × p × n é igual à quantidade de vezes que a linha 3 do pseudocódigo 
é executada. 
Na linha 3, é possível observar que a matriz C é acionada duas vezes. 
 
 
 
 
 
 
 
Soma de Matriz 
 
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 
 
 
O algoritmo tem complexidade no tempo O (m + p + n) ou O(n^2), se as matrizes 
forem quadradas de ordem n. 
Possui um tempo de execução quadrático. 
 
 
 
 
 
Analisando as funções em si, vemos que são duas propriedades diferentes, uma 
é a soma e a outra é a multiplicação. 
Como vimos acima, a complexidade de tempo de execução é diferente de cada 
algoritmo, sendo assim, a eficiência mudará devido a diferença de processando 
de um algoritmo entre o outro 
 
 
Referências 
CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 
2012. 
https://www.ime.usp.br/~song/cursos/complex/complex.html 
https://pt.wikipedia.org/wiki/Complexidade_computacional_de_opera%C3%A7
%C3%B5es_matem%C3%A1ticas 
https://docente.ifrn.edu.br/demetrioscoutinho/disciplinas/algoritmos/03-
complexidade 
 
https://www.ime.usp.br/~song/cursos/complex/complex.html
https://pt.wikipedia.org/wiki/Complexidade_computacional_de_opera%C3%A7%C3%B5es_matem%C3%A1ticas
https://pt.wikipedia.org/wiki/Complexidade_computacional_de_opera%C3%A7%C3%B5es_matem%C3%A1ticas
https://docente.ifrn.edu.br/demetrioscoutinho/disciplinas/algoritmos/03-complexidade
https://docente.ifrn.edu.br/demetrioscoutinho/disciplinas/algoritmos/03-complexidade