PDFsam_merge analise e computabilidade

Prévia do material em texto

Análise 
Complexidade 
Algoritmos
SLIDE	0	
julioc.silva@pitagoras.com.br
Professor
Professor Júlio Cesar da Silva
Graduado Exatas, TI e Filosofia
MBA, Mestre e Doutorando
Professor para Graduação desde 2011
Atua também com Tutoria de carreira, Consultoria 
Scrum
Bloger : www.esc larec imentofilosofico.org / 
www.logica.mat.br
YouTuber: Canal “Tem Lógica”
Interesses: Scrum, Lógica, Pensamento Crítico e Livros
julioc.silva@pitagoras.com.br
http://www.esclarecimentofilosofico.org
http://www.logica.mat.br
Avaliação 
Continuada
Avaliação 
Continuada
Atividades e 
Pontuação
Atividades:	(Etapa	1/Etapa2)	
Exercícios	em	sala:	60%	
Mapas	Mentais:	40%	
Avaliações	
30%	questões	conceituais	
40%	questões	intermediarias	
30%	ENADE
Apresentação 
da 
Disciplina
Unidade	 1	 |	 ALGORITMOS	 POLINOMIAIS	
EM	 LINGUAGEM	 DE	 PROGRAMAÇÃO	 DE	
CIÊNCIA	DA	COMPUTAÇÃO	
U n i d a d e	 2	 |	 C OM P L E T U D E	 E	
COMPLEXIDADE	EM	COMPUTABILIDADE	
Unidade	 3	 |	 FUNDAMENTOS	 A	 CIENCIA	
DA	COMPUTAÇÃO	E	COMPUTABILIDADE	
U n i d a d e	 4	 | O T I M I Z A Ç Ã O	 E	
COMPLEXIDADE	EM	COMPUTABILIDADE
Visão Geral
Os	 algoritmos	 fazem	 parte	 do	 dia-a-dia	
das	pessoas.		
Exemplos	de	algoritmos:	
	
instruções	para	o	uso	de	medicamentos;	
indicações	de	como	montar	um	aparelho;	
receitas.	
Visão Geral
Segundo	Dijkstra,	um	algoritmo	corresponde	
a	 uma	 descrição	 de	 um	 padrão	 de	
comportamento,	expresso	em	termos	de	um	
conjunto	finito	de	ações.	
	
Executando	 a	 operação	 a	 +	 b	 percebemos	
um	padrão	de	comportamento,	mesmo	que	
a	 operação	 seja	 realizada	 para	 valores	
diferentes	de	a	e	b.	
Visão Geral
Executando	 a	 operação	 a	 +	 b	 percebemos	
um	padrão	de	comportamento,	mesmo	que	
a	 operação	 seja	 realizada	 para	 valores	
diferentes	de	a	e	b.	
Qual	é	o	padrão	para	este	caso?		
R:	sequência	de	passos		
1)	Ler	duas	entradas	(números	inteiros)		
2)	Calcular	a	soma	das	duas	entradas	
3)	Retornar	o	resultado	da	soma		
Visão Geral
Definição:	 um	 algoritmo	 é	 um	 conjunto	
finito	 de	 instruções	 precisas	 para	
executar	uma	computação.	
	
Um	 algoritmo	 pode	 ser	 visto	 como	 uma	
ferramenta	 para	 resolver	 um	 problema	
computacional	bem	especificado			
Visão Geral
Análise:	exame	de	cada	uma	das	partes	de	
algo	composto	.	
Complexidade:	 algo	 que	 seja	 complexo,	
que	abrange	ou	encerra	muitos	elementos	
ou	partes.
Visão Geral
Computação:	relativo	a	eficiência	em	que	
um	 algoritmo	 é	 executado	 sobre	 um	
computador,	medição	da	velocidade	e	do	
desempenho.	
Visão Geral
Compu tab i l i d ade :	 a va l i a ção	 de	
algoritmos	 em	 função	 da	 computação	
destes	por	um	computador.	
Computável:	fornece	a	saída	correta	para	
cada	 entrada	 válida	 Não-computável:	
trava	para	alguma	entrada.
Visão Geral
Visão Geral
Um	 algoritmo	 não	 existe,	 ou	 seja,	 não	 é	
possível	 escrevê-lo,	 se	 antes	 não	 for	
definido	 o	 modelo	 computacional	
associado	(como	será	executado).		
Visão Geral
Visão Geral
Deve-se	 definir	 um	 repertório	 finito	 de	
regras:	As	linguagens	de	programação.	
A	 maior	 parte	 dos	 algoritmos	 utiliza	
métodos	 de	 organização	 de	 dados	
envolvidos	na	computação:	As	estruturas	
de	dados.	
Visão Geral
Tempo	finito	não	é	uma	eternidade:		
A	 maior	 parte	 das	 pessoas	 não	 está	
interessada	 em	 algoritmos	 que	 levam	
anos,	 décadas,	 Séculos,	 milênios	 para	
executarem.		
Visão Geral
Existem	diferentes	“tipos	de	computadores”.	
Existem	diferentes	modelos	computacionais:	
RAM,	PRAM,	de	pilha,	de	registro	
Visão Geral
Questão	decorrente:	
	
Dado	 um	 problema	 qualquer,	 existe	
sempre	 um	 algoritmo	 que	 pode	 ser		
projetado	 para	 um	 dado	 modelo	
computacional?	
Visão Geral
Visão Geral
Visão Geral
Visão Geral
Visão Geral
Visão Geral
Visão Geral
Visão Geral
O	problema	é	chegar	com	algoritmos	que	
os	generais	podem	usar,	incluindo	o	envio	
de	 mensagens	 e	 o	 processamento	 de	
mensagens	recebidas,	que	pode	permiti-
los	concluir	corretamente:	
Sim,	vamos	atacar	na	hora	marcada.	
Visão Geral
A	 partir	 daí	 é	 bastante	 simples	 para	 os	
generais	 chegarem	 a	um	 acordo	 sobre	 a	
hora	de	atacar	 (i.e.	 uma	mensagem	bem	
sucedida,	 com	 conf i rmação	 bem	
sucedida).	
Visão Geral
Porém,	 a	 sutileza	 do	 Problema	 dos	 Dois	
Generais	 está	 na	 impossibilidade	 de	
projetar	 algoritmos	 que	 sejam	 utilizados	
pelos	 generais	 para	 concordar	 de	 forma	
segura	com	o	enunciado	acima.
Visão Geral
O	 primeiro	 general	 pode	 começar	
enviando	 uma	 mensagem	 "Ataque	 às	
06:00	em	4	de	agosto."		
No	entanto,	uma	vez	enviada,	o	primeiro	
general	 não	 tem	 ideia	 se	 o	 mensageiro	
entregou	ou	não.		
Essa	 incerteza	 pode	 levar	 o	 primeiro	
general	a	hesitar	a	atacar,	devido	ao	risco	
de	ser	o	único	atacante.	
Visão Geral
Para	ter	certeza,	o	segundo	general	pode	
enviar	 uma	 confirmação	 de	 volta	 para	 o	
primeiro:	 "eu	 recebi	 a	 sua	 mensagem	 e	
iremos	atacar	às	06:00	em	4	de	agosto."		
No	 entanto,	 o	mensageiro	 carregando	 a	
confirmação	 pode	 ser	 capturado	 e	 o	
segundo	 general	 pode	 hesitar,	 sabendo	
que	o	primeiro	não	faria	nada	sem	a	sua	
confirmação.	
Visão Geral
Assim,	 rapidamente	 se	 torna	 evidente	
que	 não	 importa	 quantas	 rodadas	 de	
confirmação	 sejam	 feitas,	 não	 há	
maneira	de	garantir	a	segunda	condição,	
de	que	cada	general	está	ciente	de	que	o	
outro	concordou	no	plano	de	ataque.		
Seja	 qual	 for	 o	 general,	 que	 envie	 o	
último	 mensageiro,	 sempre	 estará	 na	
dúvida	se	o	mensageiro	entregou	ou	não.
Inspirações
Análise 
Complexidade 
Algoritmos
SLIDE	1	
julioc.silva@pitagoras.com.br
Revisão
Visão Geral
Revisão
Questão	decorrente:	
	
Dado	 um	 problema	 qualquer,	 existe	
sempre	 um	 algoritmo	 que	 pode	 ser		
projetado	 para	 um	 dado	 modelo	
computacional?	
Algoritmo
Etapas	 no	 desenvolv imento	 de	
algoritmos:		
Definição	do	problema	
Definição	de	um	modelo	do	problema	
Especificação	do	algoritmo		
Desenho	do	algoritmo	
Verificação	da	corretude	do	algoritmo	
Análise	do	algoritmo	
Implementação	do	algoritmo	
Teste	do	algoritmo	
Documentação	do	algoritmo	
Algoritmo
Inspirações
Modelo 
Computacional
Modelo:	 Esquema	 que	 possibilita	 a	
representação	 de	 uma	 entidade	
(Houaiss).	
No	 modelo,	 só	 se	 deve	 incluir	 o	 que	
for	 relevante	 para	 a	 modelagem	 do	
Objeto	em	questão.	
Compu t a c i o n a l :	 R e l a t i v o	 a o	
processamento	(Houaiss.)	
Modelo 
Computacional
Modelo	 computacional:	 Esquema	
que	 descreve	 como	 é	 o	 modelo	
abstrato	 do	 processamento	 de	
algoritmos.	
Modelo	 abstrato:	 define	 uma	
abstração	do	mundo	real	
Processamento	 de	 algoritmos:	 a	
forma	 como	 os	 algoritmos	 são	
p rocessados/executados	 por	
computadores	 ou	 por	 um	 modelo	
computacional
Modelo 
Computacional
Importância:	 um	 algoritmo	 não	
existe,	ou	seja,	não	é	possível	escrevê-
lo,	se	antes	não	for	definido	o	modelo	
computacional	 associado	 (como	 será	
executado).	
Define	 o	 conceito	 básico	 no	 projeto	
de	qualquer	algoritmo.	
Modela	 o	 computador	 tradicional	 e	
outros	elementos	computacionais.	
Inspirações
Inspirações
Inspirações
Modelo 
Computacional
Análise	 de	 Algoritmos:	 técnicas	 e	
metodologias	para	avaliar	a	complexidade	
de	um	dado	algoritmo	computacional:	
Notações/ordens	de	complexidade	
Técnicas	de	análise	de	algoritmos	
Paradigmas	de	projeto	de	algoritmos	
Teoria	da	complexidade	computacional	
Modelo 
Computacional
Classes	 de	 complexidade	 em	 algoritmos:	
definem	 classes	 de	 categorização	 de	
complexidades	para	os	algoritmos	
Constante	(1):	acesso	a	uma	posição	específica	
do	vetor		
Logarítmica	(logn):	busca	binária	
Linear	(n):	busca	sequencial	
LogLinear	(nlogn):	MergeSort,	QuickSort	
Quadrática	(n2):	SelectionSort,	InsertSort		
Cúb i ca	 ( n3 ) :	 b u s ca	 em	 uma	 mat r i z	
tridimensional	
Fatorial	(n!):	Fibonacci	
Exponencial	 (kn):	 caixeiro	 viajante	 por	 força	
bruta
Inspirações
Modelo 
Computacional100	 milhões	 de	 operações	 são	
executadas	em	1	segundo.	
Modelo 
Computacional
As	 técnicas	 matemáticas	 permitem	
efetuar	 uma	 análise	 precisa	 de	
algoritmos	computacionais	
Somatórios	e	produtórios	
Equações	de	recorrência	
Resolução	de	equações	de	recorrência		
Expansão	telescópica	
Substituição	
Arvores	de	recursão	
Teorema	mestre
Inspirações
Inspirações
Modelo 
Computacional
Paradigmas	de	projeto	em	algoritmos:	
fornecem	 técnicas	 de	 projeto	 de	
algoritmos	 para	 a	 resolução	 de	
problemas.	
Modelo 
Computacional
Paradigmas	de	projeto	em	algoritmos:	
Os	padrões	descrevem	técnicas	genéricas	
para	a	resolução	de	problemas		
Oferecem	técnicas	genéricas	de	projeto	e	
implementação	de	algoritmos	
Modelo 
Computacional
Paradigmas	de	projeto	em	algoritmos:	
As	 técnicas	 estão	 relacionadas	 com	 a	
natureza	do	problema.	
Exemplo:	 como	 resolver	 problemas	 que	
podemos	 descrever	 sua	 soluções	 em	
caminhos	em	árvores?	
Modelo 
Computacional
Teoria	 da	 Computabilidade:	 teoria	 da	
complexidade	computacional.		
Ramo	 da	 teoria	 da	 computação	 e	
matemática	que	foca	na	classificação	de	
problemas	 computacionais	 de	 acordo	
com	 sua	 d i f i cu ldade	 aparente ,	
relacionando	as	classes	entre	si.	
Máquina	 de	 Turing	 e	 computabilidade	
em	algoritmos.	
Completude	NP.
Modelo 
Computacional
Exercícios	de	Fixação	
1.	 Qual	 a	 melhor	 definição	 para	
algoritmo?	
2.	 Defina	 o	 que	 é	 um	 modelo	
computacional	e	qual	a	sua	relação	com	
os	algoritmos.	
3.	Qual	a	diferença	entre	RAM	e	PRAM?	
4.	 Implemente	um	algoritmo	em	C	que	
leia	 um	 vetor	 com	 cinco	 posições,	 em	
cada	posição	existe	um	número.	Após	a	
leitura	o	algoritmo	deve	 somar	os	dois	
maiores	valores.
Análise 
Complexidade 
Algoritmos
SLIDE	1	
julioc.silva@pitagoras.com.br
Revisão
1.	 Qual	 a	 melhor	 definição	 para	
algoritmo?		
2.	 Defina	 o	 que	 é	 um	 modelo	
computacional	 e	 qual	 a	 sua	 relação	
com	os	algoritmos.		
3.	 Qual	 a	 diferença	 entre	 RAM	 e	
PRAM?		
4.	Implemente	um	algoritmo	em	C	que	
leia	 um	 vetor	 com	 cinco	posições,	 em	
cada	 posição	 existe	 um	número.	 Após	
a	 leitura	 o	 algoritmo	 deve	 somar	 os	
dois	maiores	valores.	
Revisão
1.	 Qual	 a	 melhor	 definição	 para	
algoritmo?		
Definição:	 um	 algoritmo	 é	 um	
conjunto	 finito	 de	 instruções	 precisas	
para	executar	uma	computação.		
Um	 algoritmo	 pode	 ser	 visto	 como	
uma	 ferramenta	 para	 resolver	 um	
p rob lema	 computac iona l	 bem	
especificado	.
Revisão
2.	 Defina	 o	 que	 é	 um	 modelo	
computacional	 e	 qual	 a	 sua	 relação	
com	os	algoritmos.		
Um	algoritmo	não	existe,	ou	seja,	não	
é	possível	escrevê-lo,	 se	antes	não	 for	
definido	 o	 modelo	 computacional	
associado	(como	será	executado).		
O	 mode l o	 d e f i n e	 o	 q ue	 é	 o	
computador	 e	 como	 este	 executa	 o	
algoritmo.
Revisão
3.	 Qual	 a	 diferença	 entre	 RAM	 e	
PRAM?		
RAM:	 Acesso	 randômico	 a	 uma	 única	
estrutura	de	memória.	
PRAM:	Acesso	 randômico	 em	paralelo	
a	um	conjunto	de	memória.
Revisão
4.	 Implemente	 um	 algoritmo	 em	 C	
que	leia	um	vetor	com	cinco	posições,	
em	 cada	 posição	 existe	 um	 número.	
Após	a	leitura	o	algoritmo	deve	somar	
os	dois	maiores	valores.	
Complexidade 
no Tempo e 
no Espaço.
A	avaliação	do	desempenho	de	um	
algoritmo	quanto	executado	por	um	
computador	 pode	 ser	 feita	 a	
posteriori	ou	a	priori.		
	
Complexidade 
no Tempo e 
no Espaço.
A	 posteriori:	 mede	 o	 tempo	 de	
execução	 propr iamente	 d i to	
(empírico)	:	
Arquitetura		
Linguagem	Código		
Benchmarks		
	
Complexidade 
no Tempo e 
no Espaço.
A	 priori:	 feita	 sem	 sua	 execução	
(teórico):	
Considera	itens	de	entrada	
Número	de	instruções	executadas		
	
Complexidade 
no Tempo e 
no Espaço.
Exemplo:	 Suponhamos	 que	 temos	
dois	 programas	 que	 irão	 ordenar	
uma	 lista	 de	 registros	 de	 alunos	 e	
permitir	 a	busca	por	 alunos	na	 lista	
ordenada.	
Como	 s abe r	 qua l	 do s	 do i s	
algoritmos	é	o	melhor?		
	
Inspirações
Complexidade 
no Tempo e 
no Espaço.
Opções	de	solução:	
	
Em	 tempo	de	execução:	 executando	
os	programas	
	
A	 priori:	 realizando	 uma	 análise	
prévia	dos	algoritmos	usados		
	
Complexidade 
no Tempo e 
no Espaço.
O	projeto	 e	 a	 análise	 de	 algoritmos	
focam	na	análise	a	priori.	
	
Complexidade 
no Tempo e 
no Espaço.
Analisar	a	complexidade	computacional	
de	 um	 algoritmo	 significa	 prever	 os	
recursos	de	que	o	mesmo	necessitará:		
Memória	
Largura	 da	 banda	 de	 comunicação	
Hardware	
Tempo	de	execução		
	
Complexidade 
no Tempo e 
no Espaço.
Cenários	de	análise		
Melhor	 caso:	 quase	nunca	acontece	
Caso	médio:	poucas	vezes	
Pior	caso:	mais	frequente		
Dependência	 direta	 do	 estado	 da	
entrada.	Ex:	ordenação	com	o	vetor	
já	ordenado		
	
Complexidade 
no Tempo e 
no Espaço.
Pergunta:	 Qual	 é	 o	 problema	 em	
medir	 o	 tempo	 de	 execução	 de	 um	
algoritmo	em	segundos?		
	
Complexidade 
no Tempo e 
no Espaço.
Pergunta:	 Qual	 é	 o	 problema	 em	
medir	 o	 tempo	 de	 execução	 de	 um	
algoritmo	em	segundos?	
Resposta:	O	tempo	de	execução	em	
segundos	 de	 um	 mesmo	 algoritmo	
depende	de	vários	 fatores,	 inclusive	
a	máquina	onde	ele	será	executado.		
	
Complexidade 
no Tempo e 
no Espaço.
Pergunta:	 Qual	 é	 o	 problema	 em	
medir	 o	 tempo	 de	 execução	 de	 um	
algoritmo	em	segundos?	
Resposta:	O	tempo	de	execução	em	
segundos	 de	 um	 mesmo	 algoritmo	
depende	de	vários	 fatores,	 inclusive	
a	máquina	onde	ele	será	executado.	
Neste	 caso,	 é	 necessário	 calcular	 o	
número	 de	 operações	 ou	 passos	
necessários	para	a	execução	de	todo	
o	algoritmo	
Complexidade 
no Tempo e 
no Espaço.
Ge ra lmen t e	 p a r a	 um	 d a d o	
problema,	 haverá	 mais	 de	 um	
algoritmo	para	resolvê-lo.	
	
Complexidade 
no Tempo e 
no Espaço.
A	 aná l i s e	 de	 comp l ex i d ade	
computacional	 é	 fundamental	 no	
processo	de	definição	de	algoritmos	
mais	eficientes	para	a	busca	de	uma	
solução.	
	
Complexidade 
no Tempo e 
no Espaço.
Em	 geral,	 o	 tempo	 de	 execução	 e	 o	
espaço	 necessário	 em	 memória	
cresce	com	o	tamanho	da	entrada.	
		
Tempo:	 quantidade	 de	 tempo	
necessário	 para	 um	 algoritmo	
finalizar.	
Espaço:	 quantidade	 de	memória	 que	
um	algoritmo	precisa.	
	
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
Porque	 medir	 a	 complexidade	 de	
algoritmos?		
O	 tempo	 de	 computação	 e	 o	 espaço	
na	memória	são	recursos	limitados		
Os	 computadores	 podem	 ser	 rápidos,	
mas	não	são	infinitamente	rápidos		
A	 memória	 (primária	 e	 secundária)	
pode	ser	de	baixo	custo,	mas	é	finita	e	
não	é	gratuita	
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
A	taxa	de	crescimento	proporcional	de	
um	 dado	 algoritmo	 em	 função	 do	
tamanho	de	sua	entrada	é	chamada	de	
complexidade	do	algoritmo.		
	
Complexidade 
no Tempo e 
no Espaço.
Ela	 permite	 uma	 classificação	 dos	
algoritmos	 segundo	 sua	 categoria	 de	
complexidade	 e	 permite	 também	
comparar	 qualitativamente	 algoritmos	
diferentes	 que	 realizam	 a	 mesma	
tarefa.		
Pode	 ser	 considerada	 em	 termos	 de	
tempo	 de	 execução	 (complexidade	 de	
tempo)	 ou	 termos	 de	 espaço	 de	
memória	 utilizado	 (complexidade	 de	
espaço).	
Complexidade 
no Tempo e 
no Espaço.
Antes	 de	 analisarmos	 um	 algoritmo,	 é	
necessário	 termos	 um	 modelo	 da	
tecnologia	 de	 implementação	 que	 será	
usada	.	
Definição	de	um	modelo	de	 recursos	da	
tecnologia	e	seus	custos	
Complexidade 
no Tempo e 
no Espaço.
Utilização	de	um	modelo	computacional	
genérico:		
RAM	
Utiliza	somente	um	único	processador		
No	 modelo	 RAM,	 as	 instruções	 são	
executadas	 uma	 após	 a	 outra,	 sem	
operações	concorrentes	ou	simultâneas		
Tipos	 de	 dados:	 inteiros	 e	 de	 ponto	
flutuante
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempoe 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
EXEMPLO	
Complexidade 
no Tempo e 
no Espaço.
Complexidade 
no Tempo e 
no Espaço.
Análise 
Complexidade 
Algoritmos
SLIDE	3	
julioc.silva@pitagoras.com.br
Inspirações
Análise 
Assintótica
Quais	 são	 os	 problemas	 existentes	 nesta	
solução	proposta?	
	
Diferentes	 entradas	 (instâncias)	 podem	
oferecer	 resultados	diferentes	para	 ambos	
algoritmos	
Ex:	para	uma	dada	entrada	E1,	A1	foi	melhor,	mas	
para	a	entrada	E2,	A2	teve	um	melhor	resultado	
	
A	mesma	entrada	em	um	mesmo	algoritmo	
em	 diferentes	 máquinas	 (computadores)	
pode	ter	resultados	diferentes	
Ex:	para	uma	dada	entrada	E1,	A1	foi	melhor	na	
máquina	M1,	mas	foi	pior	na	máquina	M2	
Análise 
Assintótica
Análise:	estudo	de	um	elemento	por	
partes,	decomposição	
A s s i n t ó t i c a :	 d e s c r e v e	 u m	
comportamento	 de	 limite	 de	 uma	
função	 matemática	 (mínimos	 e	
máximos)		
Propõe	 em	 avaliar	 limites	 de	 uma	
função	 matemática	 em	 a	 partir	 de	
seus	termos.
Análise 
Assintótica
O	que	é	Análise	Assintótica?		
Define	 uma	metodologia	 de	 análise	
de	 algoritmos	 que	 tenta	 resolver	
estes	 e	 vários	 outros	 problemas	
relacionados	 ao	 desempenho	 de	
algoritmos.
Análise 
Assintótica
O	que	é	Análise	Assintótica?		
Permite	a	análise	de	desempenho	de	
um	algoritmo	em	função	do	tamanho	
da	entrada.	
Não	 existe	 o	 foco	 em	 tempo	 de	
execução	(segundos,	etc).	
Como	 o	 algoritmo	 se	 comporta	
(tempo	 e/ou	 espaço)	 quando	 o	
tamanho	da	entrada	é	aumentado.		
Análise 
Assintótica
Ordem	de	crescimento:		
define	 o	 impacto	 no	 desempenho	
quando	 o	 tamanho	 da	 entrada	 é		
alterado		
Inspirações
Inspirações
Análise 
Assintótica
Uso	de	três	principais	anotações:	
Notação	O		
Notação	Teta	(Θ)		
Notação	Omega	(Ω)		
Inspirações
Inspirações
Inspirações
Análise 
Assintótica
A	 Notação	 Θ	 procura	 por	 limites	
inferior	 e	 superior	 (inclusivos)	 de	
uma	função:	melhor	e	pior	casos.	
É	 necessário	 que	 exista	 apenas	 um	
limite	inferior	e	superior,	entretanto,	
podem	existir	vários		
A	 escolha	 das	 constantes	 depende	
diretamente	 da	 função	 que	 está	
sendo	analisada	
Inspirações
Inspirações
Inspirações
Análise 
Assintótica
Quando	 a	 Notação	 O	 é	 usada	 para	
expressar	 custo	 computacional	 de	
um	 algoritmo	 no	 pior	 caso	 (tempo	
ou	 espaço),	 está	 se	 definindo	
também	o	 limite	 (superior)	do	custo	
computacional	desse	algoritmo	para	
todas	as	entradas.		
Por	 exemplo,	 em	 função	 do	 tempo	
de	 execução,	 o	 algoritmo	 de	
ordenação	 por	 inserção	 é	 O(n2)	 no	
pior	caso.		
Inspirações
Inspirações
Inspirações
Inspirações
Inspirações
Análise 
Complexidade 
Algoritmos
SLIDE	4	
julioc.silva@pitagoras.com.br
Visão Geral
Seja	 A	 um	 algoritmo	 para	 um	
problema	P.		
A	 quantidade	 de	 tempo	 que	 A	
consome	 para	 processar	 uma	 dada	
instância	 de	 P	 depende	 da	 máquina	
usada	para	executar	A.		
Mas	o	efeito	da	máquina	 se	 resume	a	
uma	constante	multiplicativa:		
	
Visão Geral
Mas	o	efeito	da	máquina	 se	 resume	a	
uma	constante	multiplicativa:		
Se	 A	 consome	 tempo	 t	 numa	
determinada	 máquina,	 consumirá	
tempo	 2t	 numa	 máquina	 duas	 vezes	
mais	 lenta	 e	 t/2	 numa	máquina	 duas	
vezes	mais	rápida.		
Para	 eliminar	 o	 efeito	 da	 máquina,	
basta	discutir	o	consumo	de	tempo	de	
A	sem	as	constantes	multiplicativas.
6n2+100n+300
Inspirações
0,6n2+1000n+3000
Inspirações
Inspirações
Inspirações
Visão Geral
A	notação	assintótica	(Ο	-	ómicron,	Ω	-	
ómega,	Θ	-	teta)	é	ideal	para	fazer	isso.		
É	preciso	introduzir	um	modo	grosseiro	
de	 comparar	 funções.	 (dependência	
entre	 o	 consumo	 de	 tempo	 de	 um	
algoritmo	 e	 o	 tamanho	 de	 sua	
“entrada”).
Visão Geral
Essa	 comparação	 só	 leva	 em	 conta	 a	
“velocidade	 de	 crescimento”	 das	
funções.		
A s s im ,	 e l a	 d e s p r e z a	 f a t o r e s	
multiplicativos	 (pois	a	 função	2n2,	por	
exemplo,	 cresce	 tão	 rápido	 quanto	
10n2)	e	despreza	valores	pequenos	do	
argumento	 (a	 função	 n2	 cresce	 mais	
rápido	 que	 100n,	 embora	 n2	 seja	
menor	 que	 100n	 quando	 n	 é	
pequeno).	
Visão Geral
Esse	 tipo	 de	 matemática,	 interessado	
somente	 em	 valores	 enormes	 de	 n,	 é	
chamado	assintótica.		
Nessa	 matemática,	 as	 funções	 são	
classificadas	 em	 "ordens";	 todas	 as	
funções	 de	 uma	 mesma	 ordem	 são	
"equivalentes".		
	
Visão Geral
Inspirações
Inspirações
Inspirações
Inspirações
Inspirações
Inspirações
Inspirações
Inspirações
Visão Geral
Quando	dois	algoritmos	fazem	parte	da	
mesma	 classe	 de	 comportamento	
assintótico,	eles	são	ditos	equivalentes.		
Nesse	 caso,	 para	 escolher	 um	 deles	
deve-se	 analisar	 mais	 cuidadosamente	
a	 função	 de	 complexidade	 ou	 o	 seu	
desempenho	em	sistemas	reais.