02_Complexidade e Notacao Assintotica

Prévia do material em texto

1
Estrutura de Dados e 
Algoritmos
1
Complexidade e Notação Assintótica
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Recapitulando…
2
É importante não só ter uma 
máquina boa, mas também um 
algoritmo (tecnologia) eficiente!
É importante não só ter uma 
máquina boa, mas também um 
algoritmo (tecnologia) eficiente!
2
Perguntas pertinentes
3
� Como representar e estudar o tempo de execução
dos algoritmos?
� Como classificar os diversos algoritmos de acordo
com seus tempos de execução?
� O quão eficiente é um algoritmo?
Pontos a considerar
4
� Intruções sequenciais
� Uso de abstração (identificar termos mais
significantes nas fórmulas)
� Uso de background matemático
� Tamanho da entrada depende do problema
3
Pontos a considerar
5
� Tempo de execução = número de passos
executados
� Cada linha é executada em um tempo constante
� O número de repetições de cada linha é que será
relevante na complexidade!!!
Pontos a considerar (Exemplo)
6
Custo Quantidade Executada
Algoritmo com 
aninhamento de laços
4
Caso a Considerar
7
� Pior Caso
� É um limite superior do tempo de execução de um 
algoritmo
� Ocorre frequentemente
� O caso médio é frequentemente tão ruim quanto o pior
caso
Classes de Função
8
� O tempo de execução é uma função da entrada
� Cada função tem uma taxa de crescimento
� Uso de agrupamento de funções. Funções de mesmo
grupo tem taxa de crescimento equivalentes
5
Classes de Função
9
polinomial (quadrática, cúbica,...)
linear
constante
logarítmica
exponencial
Cada classe é caracterizada por 
uma família diferente de curva
Classes de Função
10
6
Exercício
11
� Ordene as funções por ordem de crescimento
� n5+132n2
� 3n+12
� 8900
� 45log(n)
� 45log(n).n
� 132n2
Exercício
12
� Suponha que temos dois algoritmos que ordenam 
elementos. 
� O Alg 1 pertence a classe n2
� O Alg 2 pertence a classe n.log n. 
� Qual dos dois você escolheria?
7
Cálculo do tempo: Idéia Principal
13
� Ignore constantes relacionadas ao hardware
� Foco
� Crescimento da função quando n → infinito
� Análise Assintótica
O tempo de execução cresce proporcionalmente a n
(polinomialmente, exponencialmente, 
logaritmicamente, etc.)
Análise Assintótica
14
� É uma ferramenta
para ajudar a 
estruturar nosso 
pensamento
� Eficiência assintótica: 
entradas grandes 
para tornar relevante 
apenas a ordem de 
crescimento do 
tempo de execução
8
Notação Assintótica
15
� Descreve o tempo de execução assintótica de um 
algoritmo
Notação Θ
16
� Intuição
Θ(g(n)) = {f(n) | ∃c1>0, c2>0, n0>0, 
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ∀n ≥ n0}
n
T(n) c2g(n)
f(n)
c1g(n)
n0
g(n) é um limite 
assintoticamente restrito para f(n)
função 
assintoticamente não 
negativa
Θ considera função de mesma 
classe de complexidade, pois estabelece 
limites superiores e inferiores.
9
Notação Θ
17
� Intuição
Θ(g(n)) = {f(n) | ∃c1>0, c2>0, n0>0, 
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ∀n ≥ n0}
n
T(n) c2g(n)
f(n)
c1g(n)
n0
g(n) é um limite 
assintoticamente restrito para f(n)
- Se f(n) ∈ Θ(g(n)) então dizemos que f(n) cresce tão rapidamente
quanto g(n) !
- g(n) é um limitante assintótico justo (apertado) para f(n)
Notação Θ
18
� Intuição
Θ(g(n)) = {f(n) | ∃c1>0, c2>0, n0>0, 
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ∀n ≥ n0}
n
T(n) c2g(n)
f(n)
c1g(n)
n0
g(n) é um limite 
assintoticamente restrito para f(n)
10
Exemplo
19
� f(n) = 7n4+5n2+10 e g(n) = n4
� c1 = 7 > 0
� c2 = 22 > 0
� 0 ≤ 7n4 ≤ 7n4+5n2+10 ≤ 22n4
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ Θ(n4)
Θ(g(n)) = {f(n) | ∃ c1>0, c2>0, n0>0, 
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ∀n ≥ n0}
c1g(n) c2g(n)f(n)
Lidando com a Notação Θ
20
� Remova os termos de ordem mais baixa
� Ignore as constantes da ordem mais alta
Exemplo:
� 7n4+5n2+890 ∈ Θ(n4)
remova
ignore
11
Exercício 1
21
� Qual o Θ das funções abaixo?
� 8
� 5n2+8
� 7n7+5n2+8
� 7n.logn + 5n
Exercício 2
22
� Indique pelo menos 5 funções que ∈ Θ(n3).
12
Exercício 3
23
� Justifique:
� 5n2+8n ∈ Θ(n) ?
� 7n7+5n2+8 ∈ Θ(n7) ?
� 7log n ∈ Θ(n) ?
Recapitulando
24
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
13
Recapitulando
25
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
Recapitulando
26
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (c1 + i<=n; i++) 
r=2*r;
return r;
}
14
Recapitulando
27
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (c1 + n*c2 + i++) 
r=2*r;
return r;
}
Recapitulando
28
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (c1 + n*c2 + c3*(n-1)+) 
r=2*r;
return r;
}
15
Recapitulando
29
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (c1 + n*c2 + c3*(n-1)+) 
n*c4 +
return r;
}
Recapitulando
30
� Algoritmo do cálculo de potência de 2
long potencia(int n) { 
c1 +
for (c1 + n*c2 + c3*(n-1)+) 
n*c4 +
c5
}
16
Recapitulando
31
� Algoritmo do cálculo de potência de 2
f(n) = n f(n) = Θ(n)
simplificando... Complexidade do algoritmo
long potencia(int n) { 
c1 +
for (c1 + n*c2 + c3*(n-1)+) 
n*c4 +
c5
}
f(n) = 2*c1 + c2*(n+1) + n*c3 + n*c4 + c5
Exercício 4
32
� Qual a complexidade Θ do algoritmo abaixo?
public static int soma(int[] A) {
int soma = 0;
for(int i=0;i<A.length;i++)
soma+=A[i]
return soma;
}
17
Exercício 4
33
� Qual a complexidade Θ do algoritmo abaixo?
public static int soma(int[] A) {
int soma = 0;
for(int i=0;i<A.length;i++)
soma+=A[i]
return soma;
}
c
c
n*c
Exercício 4
34
� Qual a complexidade Θ do algoritmo abaixo?
public static int soma(int[] A) {
int soma = 0;
for(int i=0;i<A.length;i++)
soma+=A[i]
return soma;
}
f(n) = n f(n) = Θ(n)
c
c
n*c
18
Notação Assintótica em Equações
35
� Abusos da notação matemática que podem facilitar 
o entendimento em alguns casos
n2+2n = Θ(n2)
∈ Conjunto de 
funções
n2+2n = Θ(n2)+n
função anônima, significando 
qualquer função em Θ(n2)
Exercício 1
36
� Seja T(n) = n2 + Θ(n). T(n) pertence a que Θ?
19
Exercício 2
37
� A afirmação n = Θ(2n+5) é verdadeira? Justifique.
Exercício 3
38
� Qual a interpretação de Θ(n)+Θ(n)=Θ(n)?
� Θ(n)+Θ(n) = Θ(n) é verdade? Justifique.
20
Exercício 4
39
� A afirmação Θ(n) = Θ(n2) é verdadeira ou falsa? 
Notação O (upper bounds)
40
� Intuição
O(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ f(n) ≤ c g(n) ∀n ≥ n0}
n
T(n) c
.
g(n)
f(n)
n0
g(n) é um limite 
assintótico superior para f(n)
- Se f(n) ∈ O(g(n)) então dizemos que f(n) cresce no máximo tão
rapidamente quanto g(n) !
- g(n) é um limitante superior assintótico para f(n)
21
Notação O (upper bounds)
41
� Intuição
O(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ f(n) ≤ c g(n) ∀n ≥ n0}
n
T(n) c
.
g(n)
f(n)
n0
g(n) é um limite 
assintótico superior para f(n)
Intuição do Big-O
42
0
20
40
60
80
100
120
140
1 2 3 4 5
tamanho da entrada
T(n
)
n0
f(n) = n2+10
5.g(n) = 5.n2
0 ≤ n2+10 ≤ 5.n2 , para n ≥ n0
f(n) é O(n2)
22
Exemplo
43
� Comparar f(n) = 7n4+5n2+10 com g(n) = n4
� 0 ≤ 7n4+5n2+10 ≤ 22n4, c = 22 > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ O(n4)
� f(n) = 7n4+5n2+10 com g(n) = n5
� 0 ≤ 7n4+5n2+10 ≤ 22n5, c = 22> 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ O(n5)
O(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ f(n) ≤ c g(n) ∀ n ≥ n0}
Exercício 1
44
� Qual o O das funções abaixo?
� 890
� 5n2+890
� 7n7+5n2+890
� 7nlogn+5n
23
Exercício 2
45
� Indique pelo menos 5 funções que ∈ O(n3).
Exercício 3
46
� log2n ∈ O(n)? 
� log2n ∈ Θ(n)?
� n2 ∈ O(2n)? 
� n2 ∈ Θ(2n)?
� 3n+1 ∈ O(5n+10)? 
� 3n+1 ∈ Θ(5n+10)?
24
Exercício 4
47
� Qual a complexidade O do algoritmo abaixo?
public static int soma(int[] A) {
int soma = 0;
for(int i=0;i<A.length;i++)
soma+=A[i]
return soma;
}
Exercício 4
48
� Qual a complexidade O do algoritmo abaixo?
f(n) = n
f(n) = O(n)
f(n) = O(n2)
f(n) = O(n3)
...
public static int soma(int[] A) {
int soma = 0;
for(int i=0;i<A.length;i++)
soma+=A[i]
return soma;
}
c
c
n*c
25
Exercício 5
49
� Qual a complexidade 
O dos algoritmos ao 
lado no pior caso? 
� Vocês conhecem 
algum algoritmo 
assintoticamente 
mais eficiente?
boolean primo(int n) { 
if (n==2) return true;
for (int i=2; i<n; i++) 
if (n%i==0) 
return false; 
return true;
}
boolean primo(int n) { 
if (n==2) return true; 
for (int i=2; i<=n/2; i++) 
if (n%i==0) 
return false; 
return true;
}
Notação Ω (lower bounds)
50
� Intuição
Ω(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ cg(n) ≤ f(n) ∀n ≥ n0}
n
T(n)
f(n)
c g(n)
n0
g(n) é um limite 
assintótico inferior para f(n)
- Se f(n) ∈ Ω(g(n)) então dizemos que f(n) cresce no mínimo tão
lentamente quanto g(n) !
- g(n) é um limitante inferior assintótico para f(n)
26
Notação Ω (lower bounds)
51
� Intuição
Ω(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ cg(n) ≤ f(n) ∀n ≥ n0}
n
T(n)
f(n)
c g(n)
n0
g(n) é um limite 
assintótico inferior para f(n)
Exemplo
52
� f(n) = 7n4+5n2+10 e g(n) = n4
� 0 ≤ 7n4 ≤ 7n4+5n2+10, c = 7 > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ Ω(n4)
� f(n) = 7n4+5n2+10 e g(n) = n
� 0 ≤ 7n ≤ 7n4+5n2+10, c = 7 > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ Ω(n)
Ω(g(n)) = {f(n) | ∃c>0, n0>0, 
0 ≤ cg(n) ≤ f(n) ∀n ≥ n0}
27
Exercício 1
53
� Qual o ordem Ω das funções abaixo?
� 890
� 5n2+890
� 7n5+5n2+890
� 7nlogn+5n
Exercício 2
54
� Indique pelo menos 5 funções que ∈ Ω(n3).
28
Exercício 3
55
� log n ∈ Ω(n)? 
� log n ∈ Θ(n)? 
� log n ∈ O(n)?
� n2 ∈ Ω(2n)? 
� n2 ∈ Θ(2n)? 
� n2 ∈ O(2n)?
56
� ( ) Sobre o gráfico acima, f(n) = O(h(n)) e i(n) = Ω(h(n)).
� ( ) Sobre o gráfico acima, g(n) = O(i(n)), i(n) = O(f(n)) e, 
portanto, g(n) = O(f(n)). 
g(n)
h(n)
f(n)
i(n)
V ou F ?
29
Notação o
57
� Intuição
o(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ f(n) < c g(n) para todo n ≥ n0}
n
T(n) c
.
g(n)
f(n)
n0
g(n) é um limite 
superior que não é 
assintoticamente 
restrito para f(n)
- Se f(n) ∈ o(g(n)) então dizemos que f(n) cresce mais lentamente 
que o(g(n)!
Notação o
58
� Intuição
o(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ f(n) < c g(n) para todo n ≥ n0}
n
T(n) c
.
g(n)
f(n)
n0
g(n) é um limite 
superior que não é 
assintoticamente 
restrito para f(n)
30
Exemplo
59
� f(n) = 7n4+5n2+10 e g(n) = n5
� 0 ≤ 7n4+5n2+10 < cn5, c > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ o(n5)
� f(n) = 7n4+5n2+10 e g(n) = n6
� 0 ≤ 7n4+5n2+10 < cn6, c > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ o(n6)
o(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ f(n) < c g(n) para todo n ≥ n0}
Exercício 1
60
� Qual o o das funções abaixo?
� 890
� 5n2+890
� 7n7+5n2+890
� 7nlogn+5n
31
Exercício 2
61
� Indique pelo menos 5 funções que ∈ o(n3).
Exercício 3
62
� log2n ∈ o(n)?
� log2n ∈ O(n)?
32
Notação ω
63
� Intuição
ω(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ cg(n) < f(n) para todo n ≥ n0}
n
T(n)
f(n)
c g(n)
n0
g(n) é um limite 
inferior que não é 
assintoticamente 
restrito para f(n)
- Se f(n) ∈ ω(g(n)) então dizemos que f(n) cresce mais rapidamente
que g(n)!
Notação ω
64
� Intuição
ω(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ cg(n) < f(n) para todo n ≥ n0}
n
T(n)
f(n)
c g(n)
n0
g(n) é um limite 
inferior que não é 
assintoticamente 
restrito para f(n)
33
Exemplo
65
� f(n) = 7n4+5n2+10 e g(n) = n3
� 0 ≤ cn3 < 7n4+5n2+10, c > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ ω(n3)
� f(n) = 7n4+5n2+10 e g(n) = n
� 0 ≤ cn ≤ 7n4+5n2+10, c > 0
� Logo, concluímos que: 
� 7n4+5n2+10 ∈ ω(n)
ω(g(n)) = {f(n) | para qualquer c>0, existe n0>0, 
0 ≤ cg(n) < f(n) para todo n ≥ n0}
Exercício 1
66
� Qual o ω das funções abaixo?
� 5n2+890
� 7n5+5n2+890
� 7nlogn+5n
34
Exercício 2
67
� Indique pelo menos 5 funções que ∈ ω(n3).
Exercício 3
68
� log2n ∈ ω(n)?
� log2n ∈ Ω(n)?
35
Relação entre Notações
69
Θ (g(n)) = O(g(n)) ∩ Ω(g(n))
Upper 
bound
Lower 
bound
Tight 
bound
ou
Recapitulando
70
n
T(n)
f(n)
c g(n)
n0
n
T(n) c
.
g(n)
f(n)
n0
n
T(n) c2g(n)
f(n)
c1g(n)
n0
Θ
Ω O
36
Propriedades das Classes de Funções
71
Definições Equivalentes
72
37
Trabalhando com limites
73
Exercício 1
74
Θ O o Ω ω
5n2+8
7n4+5n2 +8
7nlogn+5n
38
Exercício 3
75
� Faça a análise do algoritmo a seguir.
public int fatorial(int n) { 
int fat = 1;
for (int i = 1; i <= n; i++)
fat = fat * i;
return fat;
}
Exercício 4
76
� Os algoritmos
fazem a mesma
coisa?
� Qual deles é mais
eficiente? Por que?
float [] result = new float[x.length];
for(int i=0;i<x.length; i++) {
float a=0;
for(int j=0;j<=i;j++)
a = a + x[j];
result[i] = (a)/(i+1);
}
return result;
float [] result = new float[x.length];
float s=0;
for(int i=0;i<x.length; i++) {
s = s + x[i];
result[i] = s/(i+1);
}
return result;