Exercícios Análise de Agoritmos

Prévia do material em texto

UNISUL – Universidade do Sul de Santa Catarina
Curso de Ciência da Computação
Unidade de Aprendizagem: Análise de Algoritmos
Prof. Luciano José Savio
Material 01
Lista de Exercícios:
1) Dois algoritmos A e B possuem complexidade n5 e 2n, respectivamente. Você utilizaria o algoritmo B ao invés do A. Em qual caso? Exemplifique.
R.: Quando o algoritmo N for maior que 1 e menor que 23, pois quando N=1, A = 1 e B = 2, e quando N=23, A = 6436343 e B = 8388608. No intervalo entre estes apresentados anteriormente, A sempre é maior que B.
2) Uma outra métrica muito utilizada para avaliar algoritmos é a Métrica Empírica (análise experimental). Essa consiste em escolher uma métrica (tempo, número de instruções executadas, etc), propor entradas diferenciadas (geralmente com alguma característica pré-definida), ou seja, amostras. Finalmente executar o algoritmo com as entradas e analisar os resultados. Esta medida é muito utilizada para comparar dois algoritmos? Justifique.
Esta medida não é tão utilizada, pois é muito difícil montar vários ambientes de testes com varias maquinas iguais, e mesmo que as máquinas fossem perfeitamente iguais, poderia haver uma flutuação de tensão, ou algum defeito de fabricação mínimo que influenciaria nos testes.
3) Por muitas vezes damos atenção apenas ao pior caso dos algoritmos. Explique o porquê.
O pior caso de algoritmos é a métrica mais interessante de se obter, pois todos querem saber quanto tempo, no máximo, vão esperar para obter um resultado, isto é, quanto tempo o algoritmo demorara para finalizar sua execução e apresentar as respostas.
4) Encontre a equação de complexidade para a situação de pior e melhor caso para os algoritmos abaixo:
a) MAIOR (N, A) 
max ← A [ 1 ] 2 OP (consulta posição 1 e atribui a max).
para i de 2 até N faça 1+n-1+n-1 (cria i, atribui n-1 vezes, vezes e testa n-1) vezes).
	Se max < A[ i ] então 2 operações executadas n-1 vezes
max ←A[ i ] 2 operações executadas n-1 vezes
	incrementa n-1 vezes
Retorne max 1 operação
No melhor caso, n=1, então o algoritmo irá criar a variável i, atribuir o valor 2 a variável i, testar somente uma vez e retornar o valor de max. Seguindo estes dados, a equação fica 2+1+1+1, totalizando 5 operações fixas.
No pior caso, executaria 2+1+n-1+n-1+2*(n-1)+n-1 = 5n-2 operações.
b) ORDENA ( N, A) 
para i de 1 até (N – 1) faça 1 + n atribuições, n comparações 
	para j de 1 até (n – i ) faça n-1 atribuições, n-1 comparações
		se A[ j ] > A[ j + 1 ] então 4 OP 
			x ← A[ j ] 1 OP
			A[ j ] ← A[ j + 1 ] 3 OP
			A[ j + 1 ] ← x 3 OP
	n-1 incrementos
n-1 incrementos
Retorne A
c) algoritmo “BuscaPrimeiraOcorrencia”: 
j ← 1 
enquanto ( A[ j ] ≠ x ) e (j < n) faça 
	j ← j + 1 4 
fim-enquanto 
se A[ j ] ≠ x então 
	sinal ← false 
senão 
	sinal ← true 
	local ← j 
fim-senão