PGINF591 – Algoritmos e Estruturas de Dados
Análise de Complexidade
Prof. Dr. Rafael Giusti
rgiusti@[Link]
Tempo de execução do algoritmo
» Nas aulas anteriores, vimos como calcular o
tempo de um algoritmo em um modelo
simplificado de um computador...
AAlgoritmo
lgoritmo media(v)
media(v)
// v:
// v: umum vetor
vetor de
de reais
reais
Executou 1 vez para um vetor de n elementos
soma ←
soma ← 0 0
para ii de
para de 11 até
até |v|
|v| Executou n vezes
soma ←← soma
soma soma ++ v[i]
v[i]
Executou n vezes
retorne soma
retorne soma // |v|
|v|
Executou 1 vez
T(n) = 2n + 2
Casos de entradas...
» Também falamos sobre os casos mais “fáceis” e
mais “difíceis” de entradas
Algoritmo BitAtivo(v)
Algoritmo BitAtivo(v)
para ii de
para de 11 até
até |v|
|v|
se v[i]
se v[i] == 11
retorne ii
retorne
» Melhor caso (primeiro bit ativo): Tm(n) = 3
» Pior caso (último bit ativo): Tp(n) = 2n + 1
» Caso médio (bit aleatório): Ta(n) = n + 2
Análise de complexidade
» Vamos utilizar uma notação que dará um limite
superior abstrato ao tempo de execução de um
algoritmo (número de passos)
» Assim podemos comparar algoritmos de
diferentes classes sem nos prendermos a
detalhes
~ Limite superior: notação O
~ Limite inferior: notação Ω
~ Limite superior e inferior: notação Θ
Limite superior assintótico
» Dizemos uma função g(n) limita superiormente
uma função f(n) se é possível multiplicar g(n) por
uma constante c > 0 tal que f(n) ≤ c·g(n) para
valores suficientemente grandes de n
Considere duas funções, f(n) e g(n)...
f(n)
Note que g(n) é
“maior” do que f(n) g(n)
nestes trechos...
n→∞
Limite superior assintótico
» Dizemos uma função g(n) limita superiormente
uma função f(n) se é possível multiplicar g(n) por
uma constante c > 0 tal que f(n) ≤ c·g(n) para
valores suficientemente grandes de n
Entretanto, no comportamento assintótico (isto é, quando n
tende ao infinito), a função g(n) não parece “superar” f(n)
f(n)
Isso
Issoquer
querdizer
dizerque
queg(n)
g(n)não
nãoéélimite
limite
superior
superiorde
def(n)???
f(n)??? g(n)
n→∞
Limite superior assintótico
» Dizemos uma função g(n) limita superiormente
uma função f(n) se é possível multiplicar g(n) por
uma constante c > 0 tal que f(n) ≤ c·g(n) para 2g(n)
valores suficientemente grandes de n
Se multiplicarmos g(n) por
uma constante, ela supera
f(n) assintoticamente
f(n)
g(n)
g(n)éélimite
limitesuperior
superiorde
def(n)!!
f(n)!!
g(n)
n→∞
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) a seguir limita superiormente f(n)
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
10n pode parecer
maior do que n² para
n entre 1 e 5...
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
mas assintoticamente
isso não é verdade!
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
Não importa qual constante
escolhermos para multiplicar
a função g(n)….
Limite superior
» A função g(n) abaixo não limita superiormente f(n)
Não importa qual constante
escolhermos para multiplicar
a função g(n)….
...a função g(n) só será
capaz de limitar f(n) em
um intervalo finito
Notação O
» A notação O está relacionada com o limite
superior de uma função
» Dada uma função g(n) qualquer, O(g(n)) é o
conjunto de todas as funções que são limitadas
superiormente por g(n)
» Se f(n) é limitada superiormente por g(n),
então dizemos que “f(n) é O(g(n))”
Limite superior e O
Complexidade
» A função "média" é linear
» T(n) = 2n + 2
» T(n) = O(n)
» O Bubble Sort é linear no melhor caso
» T(n) = 4n - 3
» T(n) = O(n)
» O Bubble Sort é quadrático no pior caso
» T(n) = 2n² + 3n - 5
» T(n) = O(n²)
Exercício
» Encontre dois limites superiores distintos para a
função
Notação O
» Formalmente
» O(g(n)) = { f(n) : existe constantes c > 0 e
n0 > 0 tais que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ n0 }
~ É o conjunto de todas as funções que são
limitadas superiormente por g(n)
Notação O
» Formalmente
» O(g(n)) = { f(n) : existe constantes c > 0 e
n0 > 0 tais que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ n0 }
~ É o conjunto de todas as funções que são
limitadas superiormente por g(n)
Notação O
» Formalmente
» O(g(n)) = { f(n) : existe constantes c > 0 e
n0 > 0 tais que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ n0 }
~ É o conjunto de todas as funções que são
limitadas superiormente por g(n)
Notação O
» Formalmente
» O(g(n)) = { f(n) : existe constantes c > 0 e
n0 > 0 tais que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ n0 }
~ É o conjunto de todas as funções que são
limitadas superiormente por g(n)
Notação O
» Formalmente
» O(g(n)) = { f(n) : existe constantes c > 0 e
n0 > 0 tais que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ n0 }
~ É o conjunto de todas as funções que são
limitadas superiormente por g(n)
Podemos afirmar essas
igualdades como um
abuso de notação.
Exemplo
» Qual é a complexidade assintótica do algoritmo
abaixo?
Algoritmo Menor(v)
Algoritmo Menor(v)
// Entradas
// Entradas
//
// v: um
v: um vetor
vetor de
de valores
valores inteiros
inteiros
menor ←← v[1]
menor v[1]
para ii de
para de 22 até
até |V|
|V|
se v[i]
se v[i] << menor
menor
menor ←← v[i]
menor v[i]
retorne menor
retorne menor
Exemplo
» Qual é a complexidade assintótica do algoritmo
abaixo?
Algoritmo Menor(v)
Algoritmo Menor(v)
// Entradas
// Entradas
//
// v: um
v: um vetor
vetor de
de valores
valores inteiros
inteiros
menor ←← v[1]
menor v[1]
para ii de
para de 22 até
até |V|
|V|
se v[i]
se v[i] << menor
menor
menor ←← v[i]
menor v[i]
retorne menor
retorne menor
Exemplo
» Qual é a complexidade assintótica do algoritmo
abaixo?
» Veja que 3(n-1)+2 é simplesmente 3n-1
» Então se escolhermos c = 3...
Exemplo
» Qual é a complexidade assintótica do algoritmo
abaixo?
Algoritmo Duplicados(v)
Algoritmo Duplicados(v)
// v:
// v: um
um vetor
vetor de
de valores
valores inteiros
inteiros
para ii de
para de 11 até
até |V|
|V|
para jj de
para de ii ++ 11 até
até |V|
|V|
se v[i]
se v[i] == v[j]
v[j]
retorne Verdadeiro
retorne Verdadeiro
retorne Falso
retorne Falso
Exemplo
» Qual é a complexidade assintótica do algoritmo
abaixo?
» A função g(n) = n² é um limite superior para
T(n) = n² + 1 porque, considerando c=2 e n0=1
Propriedades da notação O
» Somar constantes não afeta a complexidade
O(f(n)) = O(f(n) + c)
» Exemplos
O(n² + 1) = O(n²)
O(n + 3) = O(n)
O(n - 1) = O(n)
Propriedades da notação O
» Multiplicar constantes não afeta a complexidade
O(f(n)) = O(c·f(n))
» Exemplos
O(3n) = O(n)
O(6n²) = O(n2)
O(6n² - 5) = O(n2)
Propriedades da notação O
» A soma de duas funções é O(maior)
O(f(n) + g(n)) = O(g(n))
» Exemplos
O(n² + n) = O(n²)
O(n + logn) = O(n)
O(n + n) = O(n)
Propriedades da notação O
» A soma de duas classes é O(maior)
O(f(n)) + O(g(n)) = O(g(n))
» Exemplos
O(n²) + O(n) = O(n²)
O(n) + O(logn) = O(n)
O(n) + O(n) = O(n)
Propriedades da notação O
» O produto de duas classes é o produto das funções
O(f(n))·O(g(n)) = O(f(n)·g(n))
» Exemplos
O(n)·O(n) = O(n²)
O(n)·O(logn) = O(n logn)
O(n)·O(n - 1) = O(n²)
Resumo
» A notação O define um limite superior para uma
função
Tempo do algoritmo Complexidade
T(n) = 2n² - n – 1 O(n²)
T(n) = 5·n log(n) O(n logn)
T(n) = 2n + 2 O(n)
T(n) = 4 O(1)
Em resumo...
» Constantes não afetam a complexidade
» 3n + 2 = O(n)
» 1337n + 42 = O(n)
» A soma de duas funções tem complexidade da maior
» 3n2 + 1080n = O(n2)
» 5n + log64(n) = O(n)
» O produto de duas funções tem complexidade do
produto das complexidades
» f(n) = 10n2 + 5n f(n) = O(n2)
» g(n) = 5log(n) g(n) = O(log n)
» f(n)·g(n) = O(n2)·O(log n) = O(n2·log n)
Em resumo...
» Constantes não afetam a complexidade
» 3n + 2 = O(n)
» 1337n + 42 = O(n)
Essas regras podem nos ajudar a calcular
» A soma de duas
o limite funções
superior tem
dos tempos dos complexidade
algoritmos da maior
de maneira muito mais simples!
» 3n2 + 1080n = O(n2)
» 5n + log64(n) = O(n)
» O produto de duas funções tem complexidade do
produto das complexidades
» f(n) = 10n2 + 5n f(n) = O(n2)
» g(n) = 5log(n) g(n) = O(log n)
» f(n)·g(n) = O(n2)·O(log n) = O(n·log n)
Avaliação "simplificada" de complexidade
» Em vez de calcular exatamente o número de
passos, podemos encontrar sua complexidade em
notação O
» Linhas em sequência somam
» Laços de repetição multiplicam com o corpo
ii ←← 11
ii ←← ii ++ 11
Quais são as complexidades desses exemplos?
O(1) O(1)
O(1)
» Em vez de calcular
O(1)exatamente o número de
Algoritmo Menor3(a,
Algoritmo Menor3(a, b,
b, c)
c)
passos, podemos
Algoritmo
Algoritmo Soma(a, encontrar
Soma(a, b)
b) sua complexidade em
notação O se aa << bb
se
retorne a + b
retorne a + b
menor ←← aa
menor
» Linhas em sequência somam
O(1)
O(1) senão
senão
» Laços de repetição multiplicam com o corpo
Algoritmo Menor(a,
Algoritmo Menor(a, b)
b) menor ←← bb
menor
se aa << bb
se fim se
se
fim
retorne aa
retorne se cc << menor
menor
ii ←← 11 se
senão
senão menor ←← cc
ii ←← ii ++ 11 menor
retorne bb
retorne fim se
se
fim
retorne menor
retorne menor
Avaliação "simplificada" de complexidade
» Em vez de calcular exatamente o número de
passos, podemos encontrar sua complexidade em
notação O
» Linhas em sequência somam
» Laços de repetição multiplicam com o corpo
soma ←← 00
soma
para ii de
para de 11 até
até |V|
|V|
soma ←← soma
soma soma ++ v[i]
v[i]
Avaliação "simplificada" de complexidade
» Em vez de calcular exatamente o número de
passos, podemos encontrar sua complexidade em
notação O
» Linhas em sequência somam
» Laços de repetição multiplicam com o corpo
soma ←← 00
soma
para ii de
para de 11 até
até |V|
|V|
soma ←← soma
soma soma ++ v[i]
v[i]
Algoritmo BubbleSort(A)
Algoritmo BubbleSort(A)
para ii de
para de nn até
até 2,
2, passo
passo -1
-1
trocou ←← Falso
trocou Falso
para jj de
para de 11 até
até ii -- 11
se A[j]
se A[j] >> A[j
A[j ++ 1]
1]
troque A[j]
troque A[j] ee A[j
A[j ++ 1]
1] E o Bubble Sort? Tem um
jeito mais simples de
trocou ←← Verdadeiro
Verdadeiro analisar esse algoritmo?
trocou
se não
se não trocou
trocou
retorne
retorne
Bubble Sort Otimizado
Algoritmo BubbleSort(A)
Algoritmo BubbleSort(A)
para ii de
para de nn até
até 2,
2, passo
passo -1
-1
trocou ←← Falso
trocou Falso
para jj de
para de 11 até
até ii -- 11
se A[j]
se A[j] >> A[j
A[j ++ 1]
1]
troque A[j]
troque A[j] ee A[j
A[j ++ 1]
1]
trocou ←← Verdadeiro
trocou Verdadeiro
se não
se não trocou
trocou
Note que o tempo do Bubble Sort
retorne
retorne depende desses dois laços de repetição.
Então poderemos encontrar o tempo
final pelo produto das complexidades.
Bubble Sort Otimizado
Algoritmo BubbleSort(A)
Algoritmo BubbleSort(A)
para ii de
para de nn até
até 2,
2, passo
passo -1
-1
trocou ←← Falso
trocou Falso
para jj de
para de 11 até
até ii -- 11
se A[j]
se A[j] >> A[j
A[j ++ 1]
1]
troque A[j]
troque A[j] ee A[j
A[j ++ 1]
1]
trocou ←← Verdadeiro
trocou Verdadeiro
se não
se não trocou
trocou
No pior caso, ambos os laços vão executar
retorne
retorne o maior número de passos. O tempo de
execução dos dois laços é limitado pela
função g(n) = n, portanto ambos são O(n).
8
6 5
7 6
4 3
5 4
2 31 2 1
Bubble Sort Otimizado
Algoritmo BubbleSort(A)
Algoritmo BubbleSort(A)
para ii de
para de nn até
até 2,
2, passo
passo -1
-1
trocou ←← Falso
trocou Falso
para jj de
para de 11 até
até ii -- 11
se A[j]
se A[j] >> A[j
A[j ++ 1]
1]
troque A[j]
troque A[j] ee A[j
A[j ++ 1]
1]
trocou ←← Verdadeiro
trocou Verdadeiro
se não
se não trocou
trocou
Já no melhor caso, a flag "trocou" vai
retorne
retorne permitir interromper o algoritmo na
primeira iteração do laço externo. Ele só
executará uma vez. Portanto pode ser
limitado superiormente por g(n) = 1.
1 2 3 4 5 6 7 8
Complexidade do Bubble Sort
» Pior caso O(n²)
» Melhor caso O(n)
» Caso médio O(n²)
Complexidade do Bubble Sort
» Pior caso O(n²)
» Melhor caso O(n)
» Caso médio O(n²)
Nós não analisamos o caso médio na aula.
O caso médio depende da probabilidade
de obtermos instâncias mais ou menos
"difíceis" para o algoritmo.
Exercício
» Qual a complexidade do algoritmo abaixo?
»» Algoritmo MatMul(A,
Algoritmo MatMul(A, B):
B):
// Entrada:
// Entrada: duas
duas matrizes
matrizes quadradas
quadradas
//
// de ordem
de ordem nn
// Saída
// Saída :: matriz
matriz de
de ordem
ordem nn
CC == zeros(nlinhas(A),
zeros(nlinhas(A), ncolunas(B))
ncolunas(B))
para ii de
para de 11 até
até nlinhas(A)
nlinhas(A)
para jj de
para de 11 até
até ncolunas(B)
ncolunas(B)
para kk de
para de 11 até
até ncolunas(A)
ncolunas(A)
C[i, j]
C[i, j] +=
+= A[i,
A[i, k]
k] ** B[k,
B[k, j]
j]
retorna CC
retorna
Notação Ω
» A notação Ω estabelece um limite inferior para uma
função
» Ω(g(n)) = { f(n) : existe constantes c > 0 e n0 > 0 tais que 0
≤ cg(n) ≤ f(n) para todo n ≥ n0 }
~ É o conjunto de toda as funções que são limitadas
inferiormente por g(n)
Notação Ω
» A notação Ω estabelece um limite inferior para uma
função
» Ω(g(n)) = { f(n) : existe constantes c > 0 e n0 > 0 tais que 0
≤ cg(n) ≤ f(n) para todo n ≥ n0 }
~ É o conjunto de toda as funções que são limitadas
inferiormente por g(n)
Notação Ω
Notação Ω
Propriedades da notação Ω
» A notação Ω obedece propriedades bem
semelhantes à notação O
Ω(n + 5) = Ω(n)
Ω(3n) = Ω(n)
Ω(n²)·Ω(log n) = Ω(n² logn)
» E a soma de dois limites inferiores?
Ω(n) + Ω(n²) = ?
Notação Θ
» A notação Θ (theta) designa uma família de funções que
crescem junto com a função que estamos analisando
» Θ(g(n)) = { f(n) : existem constantes c1 > 0, c2 > 0 e n0 > 0
tais que, para todo n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }
~ A função g(n) pode ser vista simultaneamente como um
limite superior e inferior para f(n)
Notação Θ
» A notação Θ (theta) designa uma família de funções que
crescem junto com a função que estamos analisando
» Θ(g(n)) = { f(n) : existem constantes c1 > 0, c2 > 0 e n0 > 0
tais que, para todo n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }
~ A função g(n) pode ser vista simultaneamente como um
limite superior e inferior para f(n)
Notação Θ
» A notação Θ (theta) designa uma família de funções que
crescem junto com a função que estamos analisando
» Θ(g(n)) = { f(n) : existem constantes c1 > 0, c2 > 0 e n0 > 0
tais que, para todo n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) }
~ A função g(n) pode ser vista simultaneamente como um
limite superior e inferior para f(n)
Notação Θ
2n² = Θ(n²)
Notação Θ
logb(n) = Θ(log n)
c2 = 1
c1 = 1
log5(6)