lista 2-PAA

Prévia do material em texto

Lista	de	Exercícios	2	
	
1. Dadas	 as	 definições	 das	 notações	 assintóticas	 O,	 Ω	 e	 Θ,	 verifique	 as	
expressões	 abaixo.	 Para	 tanto,	 identifique	 constantes	 que	 validem	 a	
inequação,	 caso	 a	 expressão	 esteja	 correta,	 ou	 prove	 que	 tá	 errada	 por	
absurdo.		
a. 3n2	+	n	=	Ω(n)	
b. 3n2	+	n	=	O(n)		
c. 2n2	+	10	=	O(n3)	
d. 2n2	+	10	=	O(n2)	
e. 4n	+7	=	O(n)	
f. 2n2	+	n	=	O(n)	
g. 1/2n2	-3n	=	Θ(n2)	
	
2. Considere	 o	 problema	 de	 pesquisar	 um	 elemento	 em	 um	 vetor:		
Entrada:	Uma	sequência	de	n	números	A	=	<a1,	a2,	...,	an	>	e	um	valor	v.		
Saída:	Um	índice	i	tal	que	A[i]	=	v	ou	0	caso	v	não	seja	encontrado	em	
A.	O	 algoritmo	 de	 pesquisa	 linear	 percorre	 o	 vetor	 sequencialmente	
procurando	pelo	valor	v.		
a. Escreva	 o	 algoritmo	 de	 pesquisa	 linear	 (utilize	 a	 pseudo-
linguagem	do	livro	ou	a	linguagem	C)	�.	
b. Considere	que	v	sempre	está	presente	em	A.	Qual	é	a	função	de	
complexidade	do	seu	algoritmo	para	o	número	de	comparações	
de	elementos	no	melhor	e	no	pior	caso.	
	
3. Reescreva	o	procedimento	MERGE	de	modo	que	ele	não	utilize	sentinelas	
(∞)	e,	em	vez	disso,	se	interrompa	depois	que	o	arranjo	L	ou	R	tiver	todos	
os	seus	elementos	copiados	de	volta	para	A,	e	então	copie	o	restante	do	
outro	arranjo	de	volta	em	A.		
	
4. 	Voltando	 ao	 problema	 da	 pesquisa	 (questão	 2)	 	 observe	 que,	 se	 a	
sequência	 A	 estiver	 ordenada,	 poderemos	 comparar	 o	 ponto	 médio	 da	
sequência	 com	 v	 e	 eliminar	 metade	 da	 sequência	 de	 consideração	
posterior.	 A	 pesquisa	 binária	 é	 um	 algoritmo	 que	 repete	 esse	
procedimento,	 dividindo	 ao	 meio	 o	 tamanho	 da	 porção	 restante	 da	
sequência	 a	 cada	 vez.	 Escreva	 pseudocódigo,	 sendo	 ele	 iterativo	 ou	
recursivo,	para	pesquisa	binária.	Demonstre	que	o	tempo	de	execução	do	
pior	caso	da	pesquisa	binária	é	O(lg	n).