Teoria de Grafos - Aula 1 - Análise de Complexidade em Algoritmos

Prévia do material em texto

Complexidade de Tempo
Porque ela é importante
CAIO ANDRÉ
FORT 2ATÉN 1 FOR ir 2ATÉ nn
sei DIVIDE N sei DIVIDE N
N NÃOERRIMO NNÃOÉPRIMA
Tempo an On Tempo dar OIM
CORRETOS
CONSIDERANDO 1ms PARA REALIZAR UMA Divisa
n caia ln 2VEZES André M 1 vezes
11 9ms 2ms
101 99ms 9ms
106 3 16,66min 1 seg10719 dias 1,66mi
Como analisar a complexidade de tempo
O tempo de execução depende de
1 A sua máquina tem um único núcleo de
processamento ou multiples
motim
Amençoçouçaçu
de escrita e leitura para
3 Da arquitetura do sistema hoje em dia
no gonal seriam 32 ou 646in a arquitetura
ademos
Jim µ Dados de entradadeforma Relação entre o crescimentorodável da entrada e o aumento do tempo
Como é analisarmos a entrada utiliza se uma máquina
modelo i
MÁQUINA MODELO
Um único núcleo de processamento
32 bits
sequencial
1 u.to unidade de tempospara operações
aritméticas
do e para atribuição e retorno
Exemplo 1 Soma de dois números
SOMA A B
RETORNA Ato T soma Lot
IV t Ju
Exemplo 2 Soma dos elementos de uma lista
SOMALISTA AM CUSTO N VEZES TOTAL
TOTAL 0 d 1 1
FOR F 0 ATÉ N 1 2 2h2
TOTAL TOTAL.tt 2 n 2N
RETORNA TOTAL 1 1 1
Untus
K 1 1 1
te
Atentativade continuar
no loopmasnãoentra
uafjoe EEE.jo
Análise Assintótica quando n tende ao infinito
Toma K O a
T.sn cu td 0 n
µ
an t but a 0 na
Ir
á TAMANISTA
FOMA
n
Notações Assintóticas
ALGORITMO 1 T n Sua 7 NA MÁQUINA
ALGORITMO 2 T n 17H Guto MODELO
1 n n
2 NÃO CONSIDERAR AS CONSTANTES
ALGO 1 e ALGO 2 têm a mesma taxa de
néscimento quadrática
Definições
O Big OH Limite superior
Orsini frentes ecá
Ex i f n SE e 2N t 1
g n na
f n 5Mt 2nt 1 E 542 t 2Mt en Eu
e D no 1
fin Ana
Porque 5m42cm1 e Sit 2kt vi
Sei que 5M Sei 5Mt2g 5h42m 5m42s e5h42E
podeser negativo do
quero o ladodireito Suit2nte Soft2nFmaiorqueesqPosso Ebitdaconsiderar n n
equero o sado
jijeitgemfunção logo5h42min8h
M Omega Limite inferior
d gent Fln Joeno agente FH traz
F n 5 n t 2Mt 1
96ns na
Srf e 5h 2h 1
C S no O i Fln Algen
THETA Limite justo
gens Fn Fln Ngm n Fln Mgm
f h 5m42 n t 1
G n n2
c 8 5 no 1 i Fm 0 gent
n
t.fi