Solucao Exercicios aulas 07, 08 e 09

Prévia do material em texto

Universidade Federal de Minas Gerais 
Departamento de Ciência da Computação 
Algoritmos e Estruturas de Dados II 
2º Semestre de 2011 
 
Solução dos Exercícios Aula 07, 08 e 09.pdf 
 
1. 
•••• A função p1 calcula a multiplicação da matriz A pela matriz B e coloca o resultado na matriz C. 
•••• A operação relevante é o número de operações de multiplicação e soma realizadas com os elementos 
dos vetores. 
 
∑∑∑
−
=
−
=
−
=
===
1
0
1
0
1
0
32...2)(
n
i
n
j
n
k
nnT 
)()( 3nOnT = 
 
2. A função p2 calcula o seguinte somatório: 
∑∑
= =
+
===
n
i
n
ij
nn
x
1
2
2
...1 
∑∑
=
−
=
−
===
n
i
i
j
nny
1
21
1 2
...1 
 
Considerando que a operação relevante seja o número de operações de soma realizadas com as variáveis x 
e y: 
 
∑ ∑ ∑
= =
−
=
==







+=
n
i
n
ij
i
j
nnT
1
2
1
1
...11)( 
)()( 2nOnT = 
 
3. 
Vamos analisar as listas de comandos dentro do IF e do ELSE para verificar qual delas executa o maior 
número de operações. 
IF 
1...1)(
1
1
−−=== ∑
−
+=
innT
n
ij
 
ELSE 
111)(
1
0
+=+= ∑
−
=
nnT
n
j
 
Portanto, o pior caso será alcançado quando os comandos do ELSE forem sempre executados, ou seja, 
quando todos os elementos de x forem menores ou iguais a 10. Neste caso, 
 
∑
−
=
+==+=
1
0
2
...)1()(
n
i
nnnnT 
4. 
 
int exprec(int n) { 
 if (n<=0) 
 return(1); 
 else 
 return(2*(exprec(n-1))); 
} 
 
5. Retorna o máximo divisor comum dos números a e b. 
 
6. 
a) nnT log)( = 
b) nnnT log)( = 
c) 
2
13)( −= nnT 
 
7. 



==
=
2loglog 42
)(
nnn
nnf
a
b
 
 ( )12−= nOn 
( )nOn = 
( )2)( nnT Θ=