Exercícios 3 e 4 - Complexidade de Algoritmos

Prévia do material em texto

Nome: Raquel Alves Fontes RGM: 30109884
Prof. Manuel Fdez. Paradela Ledón - ED-I. - Ciências da Computação - 3D
________________________________________________________________
Exercícios 3 e 4 - Complexidade de Algoritmos.
3) Suponha:
	a) n=1. Quanto vale k ao final do loop?
	R: 1.
b) n=2. Quanto vale k ao final do loop?
R: 2.
c) n=4. Quanto vale k ao final do loop?
R: 3.
d) n=8. Quanto vale k ao final do loop?
	R: 4.
e) Compare os resultados com e apresente uma conclusão 
R: Pelo fato do loop while apenas encerrar no momento que i > 0 for falso, ainda é considerado o valor de i = 1 dividindo e executado mais uma vez, também incrementando 1 para k, antes de i<=0
Contudo, em um loop do tipo log2(n), é possível observar que o loop para no momento que i > 1 é falso. Sendo assim um resultado preciso para qualquer valor de entrada no algoritmo:
log2(8) = 3. 
4) Suponha:
a) n=1. Quanto vale k ao final do loop?
		R: 1.
b) n=10. Quanto vale k ao final do loop?
R: 4.
c) n=100. Quanto vale k ao final do loop?
R: 7.
d) n=1000. Quanto vale k ao final do loop?
R: 10
e) Compare os resultados com log10(n) e apresente uma conclusão
R: Novamente, o código considera o valor de i até que chegue a
soma mais uma vez antes de i > 0 virar falso.
Outra coisa divergente, é o fato de i ainda ser dividido por 2. Já com o loop no modelo log10(n), primeiro trocamos os valores de entrada: 1, 10, 100, 1000, depois o limite para i, por fim, k passa a ser dividido por 10, assim fazendo com que o loop dure menos tempo e retorne os resultados: 0,1, 2, 3, respectivamente:
log10(1000) = 3.