Slide com respostas

Prévia do material em texto

Análise e Projeto de Algoritmos
Análise de Complexidade
Exercícios
Prof. Rodrigo Freitas Silva
rodrigo.f.silva@ufes.br
Prof. Rodrigo Freitas Silva / UFES 1
Algoritmos: Eficiência
o Exemplo: Merge Sort (c2n lg n) X Insertion Sort (c1n2)
o Suponha dois computadores A e B
• A executa 10M (107) instruções por segundo
• B executa 1G (109) instruções por segundo
• Ou seja, B é 100 vezes mais rápido que A
o Merge Sort (digamos 50n lg n) implementado em A
o Insertion Sort (digamos 2n2) implementado em B
o O que acontece quando ordenamos um vetor de um milhão (106) de elementos?
o Qual algoritmo é mais rápido?
Prof. Rodrigo Freitas Silva / UFES 2
Algoritmos: Eficiência
o Exemplo: Merge Sort (c2n lg n) X Insertion Sort (c1n2)
o Merge Sort (50n lg n) implementado em A (107 instruções/segundo)
50 106 lg 106 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠
107 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠/𝑠𝑒𝑔𝑢𝑛𝑑𝑜
= ~100 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
o Insertion Sort (2n2) implementado em B (109 instruções/segundo)
2(106)2 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠
109 𝑖𝑛𝑠𝑡𝑟𝑢çõ𝑒𝑠/𝑠𝑒𝑔𝑢𝑛𝑑𝑜
= 2000 𝑠𝑒𝑔𝑢𝑛𝑑𝑜𝑠
Prof. Rodrigo Freitas Silva / UFES 3
o A executou 20 vezes mais rápido do que B !!!
o Se o vetor tivesse 10 milhões de elementos, a razão seria de 2.3 dias para 20 minutos !!!
Exemplo: Algoritmo para encontrar o menor elemento
o Considere o algoritmo para encontrar o menor elemento de um vetor de 
inteiros A[1..n]; n ≥ 1 
Function Min (var A: Vetor): integer;
var i, Temp: integer;
begin
Temp := A[1];
for i:=2 to n do
if Temp > A[i] then
Temp := A[i];
Min := Temp;
end;
o Se A contiver n elementos, temos:
o f(n) = n – 1 para n ≥ 1
o Vamos provar que o algoritmo apresentado no programa acima é ótimo
Prof. Rodrigo Freitas Silva / UFES 4
Exemplo: Algoritmo para encontrar o menor elemento
o Teorema: Qualquer algoritmo para encontrar o menor elemento de 
um conjunto com n elementos, n ≥ 1, faz pelo menos n - 1 
comparações
o Prova: Cada um dos n - 1 elementos tem de ser mostrado, por meio 
de comparações, que é menor do que algum outro elemento
o Logo n - 1 comparações são necessárias
O teorema acima nos diz que, SE o número de comparações for utilizado 
como medida de custo, então a função Min do programa anterior é ótima
Prof. Rodrigo Freitas Silva / UFES 5
POSCOMP 2003
o Qual é o número mínimo de comparações necessárias para 
encontrar o menor elemento de um conjunto qualquer não ordenado 
de n elementos?
a) 1
b) n – 1
c) n
d) n + 1
e) n log n
Prof. Rodrigo Freitas Silva / UFES 6
POSCOMP 2003
o Qual é o número mínimo de comparações necessárias para 
encontrar o menor elemento de um conjunto qualquer não ordenado 
de n elementos?
a) 1
b) n – 1
c) n
d) n + 1
e) n log n
Prof. Rodrigo Freitas Silva / UFES 7
o Quanto vale k no fim da execução do seguinte trecho de código?
a) n – 1
b) N
c) (n2 - n)/2
d) n(n + 1)/2
e) n3
POSCOMP 2004
k = 0
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++ )
k = k + 1
Prof. Rodrigo Freitas Silva / UFES 8
o Quanto vale k no fim da execução do seguinte trecho de código?
a) n – 1
b) N
c) (n2 - n)/2
d) n(n + 1)/2
e) n3
o Equivale a verificar o número de operações de atribuição (k = k + 1) são executadas, 
sendo que cada operação desta possui custo 1. Logo:
σ𝑖=1
𝑛 σ𝑗=𝑖
𝑛 1 = σ𝑖=1
𝑛 𝑖 = 1 + 2 + ... + (n - 2) + (n – 1) + n = 
𝑛(𝑛+1)
2
POSCOMP 2004
k = 0
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++ )
k = k + 1
Prof. Rodrigo Freitas Silva / UFES 9
o Complexidade do caso médio: 
o Toda pesquisa recupera um registro
o Seja pi for a probabilidade do i-ésimo registro ser procurado, e que para recuperar o i-
ésimo registro são necessárias i comparações, então
f(n) = 1 x p1 +2 x p2 +3 x p3 + ... +n x pn
o Para calcular f(n) basta conhecer a distribuição de probabilidades pi.
o Considerando que cada registro tenha a mesma probabilidade de ser acessado que todos 
os outros, então pi = 1/n; 1 ≤ i ≤ n. 
o Complexidade do caso médio = σ𝑖=1
𝑛 𝑝𝑖𝑡𝑖 = 
1
𝑛
(1+2+3+...+n) = 
1
𝑛
(n(n+1)
2
= 
n+1
2
o A análise do caso médio revela que uma pesquisa com sucesso examina 
aproximadamente metade dos registros
Exemplo Caso Médio : Registros de um Arquivo
Prof. Rodrigo Freitas Silva / UFES 10
POSCOMP 2002
o Considere o algoritmo da busca sequencial de um elemento em um 
conjunto com n elementos? A expressão que representa o tempo 
médio de execução desse algoritmo para uma busca bem sucedida é?
a) n2
b) n(n + 1)/2
c) log2n
d) (n + 1)/2
e) n log n
Prof. Rodrigo Freitas Silva / UFES 11
POSCOMP 2002
o Considere o algoritmo da busca sequencial de um elemento em um 
conjunto com n elementos? A expressão que representa o tempo 
médio de execução desse algoritmo para uma busca bem sucedida é?
a) n2
b) n(n + 1)/2
c) log2n
d) (n + 1)/2
e) n log n
Prof. Rodrigo Freitas Silva / UFES 12
POSCOMP 2006
o Dada uma lista linear de n+1 elementos ordenados e alocados 
sequencialmente, qual é o número médio (número esperado) de 
elementos que devem ser movidos para que se faça uma inserção na 
lista, considerando-se igualmente prováveis as n+1 posições de 
inserção?
a) n /2
b) (n + 2)/2
c) (n - 1)/2
d) n(n + 3 + 2/n)/2
e) (n + 1)/2
Prof. Rodrigo Freitas Silva / UFES 13
POSCOMP 2006
o Dada uma lista linear de n+1 elementos ordenados e alocados 
sequencialmente, qual é o número médio (número esperado) de 
elementos que devem ser movidos para que se faça uma inserção na 
lista, considerando-se igualmente prováveis as n+1 posições de 
inserção?
a) n /2
b) (n + 2)/2
c) (n - 1)/2
d) n(n + 3 + 2/n)/2
e) (n + 1)/2
Prof. Rodrigo Freitas Silva / UFES 14
POSCOMP 2006
o Dada uma lista linear de n+1 elementos ordenados e alocados sequencialmente, qual é o número 
médio (número esperado) de elementos que devem ser movidos para que se faça uma inserção na lista, 
considerando-se igualmente prováveis as n+1 posições de inserção?
o Considerando n+1 entradas sendo Ei, 1 ≤ i ≤ n+1, e que:
o Se a inserção for na 1º posição, n+1 nº seriam movidos
o Se a inserção for na 2º posição, n nº seriam movidos
o Se a inserção for na 3º posição, n-1 nº seriam movidos
o ...
o Se a inserção for na penúltima posição, 1 nº seria movidos
o Se a inserção for na última posição, 0 nº seriam movidos
o Probabilidade pi =
1
𝑛+1
Complexidade do caso médio = σ𝑖=1
𝑛+1 𝑝𝑖𝑡𝑖 = 
1
𝑛+1
∗ (1+2+...+n+(n+1)) =
1
𝑛+1
* 
𝑛+1(𝑛+1+1)
2
= 
𝑛+2
2
Prof. Rodrigo Freitas Silva / UFES 15
o Problema 3: Considere o algoritmo da busca sequencial de um
elemento em um vetor com n elementos. Considere que o elemento
procurado tenha probabilidade de
3
4
de estar na primeira metade do
vetor, ou seja, de estar em 1, ... ,
𝑛
2
, e que tenha probabilidade de
1
4
de estar na segunda metade do vetor, ou seja, em
𝑛
2
+1, ... ,𝑛 . Qual é
o número médio de comparações efetuadas nesse algoritmo para
uma busca bem sucedida?
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 16
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1
2
4𝑛
𝑛
2
+2
𝑛
2
+2
2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em ቂ1,
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 17
Probabilidade 
de ocorrência
3
4
1
4
൙
3
4
𝑛
2
=
6
4𝑛
൙
1
4
𝑛
2
=
2
4𝑛
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1
2
4𝑛
𝑛
2
+2
𝑛
2
+2
2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em ቂ1,
Exemplo Caso Médio : Busca Sequencial
Prof. RodrigoFreitas Silva / UFES 18
𝑓 𝑛 =෍
𝑖=1
𝑛
𝑝𝑖𝑡𝑖 =෍
𝑖=1
𝑛
2
6
4𝑛
𝑖 + ෍
𝑖=
𝑛
2
+1
𝑛
2
4𝑛
𝑖 =
6
4𝑛
෍
𝑖=1
𝑛
2
𝑖 +
2
4𝑛
෍
𝑖=
𝑛
2
+1
𝑛
𝑖
o Sabe-se que:
Soma dos termos de uma PA = 
𝑛(𝑎1+𝑎𝑛)
2
Posição 
Vetor
ti pi
1 1 6
4𝑛
2 2 6
4𝑛
... ... 6
4𝑛
𝑛
2
𝑛
2
6
4𝑛
𝑛
2
+1
𝑛
2
+1
2
4𝑛
𝑛
2
+2
𝑛
2
+2
2
4𝑛
... ... 2
4𝑛
n n 2
4𝑛
o Problema 3: Considere o algoritmo da busca sequencial de um elemento em um vetor com n elementos. Considere
que o elemento procurado tenha probabilidade de
3
4
de estar na primeira metade do vetor, ou seja, de estar em
1, ... ,
𝑛
2
, e que tenha probabilidade de
1
4
de estar na segunda metade do vetor, ou seja, em
𝑛
2
+1, ... ,𝑛 . Qual é o
número médio de comparações efetuadas nesse algoritmo para uma busca bem sucedida?
Exemplo Caso Médio : Busca Sequencial
Prof. Rodrigo Freitas Silva / UFES 19
𝑓 𝑛 =෍
𝑖=1
𝑛
𝑝𝑖𝑡𝑖 =෍
𝑖=1
𝑛
2
6
4𝑛
𝑖 + ෍
𝑖=
𝑛
2
+1
𝑛
2
4𝑛
𝑖 =
6
4𝑛
෍
𝑖=1
𝑛
2
𝑖 +
2
4𝑛
෍
𝑖=
𝑛
2
+1
𝑛
𝑖
𝑓 𝑛 =
3
4
𝑛
2
∗
𝑛
2
1 +
𝑛
2
2
+
1
4
𝑛
2
∗
𝑛
2
𝑛
2
+ 1 + 𝑛
2
𝑓 𝑛 =
3+
3𝑛
2
8
+
𝑛
2
+1+𝑛
8
=
3𝑛+4
8
Notação Θ: Exemplo 1
Prof. Rodrigo Freitas Silva / UFES 20
o Mostrar que: 
1
2
n2 – 3n = Θ (n2)
Para provar esta afirmação, devemos achar as constantes c1 > 0, c2 > 0, n > 0, 
tais que:
c1n
2 ≤ 
1
2
n2 – 3n ≤ c2n
2 para todo n ≥ no
Se dividirmos a expressão acima por n2 temos:
c1 ≤ 
1
2
-
3
𝑛
≤ c2
Notação Θ: Exemplo 1
o A inequação mais a esquerda será sempre válida para qualquer valor de n≥7 ao 
escolhermos c1 = 
1
14
o A inequação mais a direita será sempre válida para qualquer valor de n ≥1 ao 
escolhermos c2 = 
1
2
Assim, ao escolhermos c1 = 
1
14
, c2 = 
1
2
e n0 = 7, podemos verificar que que:
1
2
n2 – 3n = Θ(n2)
c1 ≤ 
1
2
-
3
𝑛
≤ c2
Prof. Rodrigo Freitas Silva / UFES 21
c1 ≤ 
1
2
-
3
𝑛
≤ c2
Notação Θ: Exemplo 1
o Mas porque c1 = 
1
14
e n0 = 7 ?
o Lembrando que as constantes devem ter os valores: c1 > 0, c2 > 0, n0 > 0
o Vamos supor que gostaríamos de obter os valores de c1 para outros valores de n0, teríamos:
Prof. Rodrigo Freitas Silva / UFES 22
c1 ≤ 
1
2
-
3
𝑛
≤ c2
n0 c1
1 ≤ -
5
2
2 ≤ -1
3 ≤ -
1
2
4 ≤ -
1
4
5 ≤ -
1
10
6 ≤ 0
7 ≤ 
1
14
c1 ≤ 
1
2
-
3
𝑛
c1 ≤ 
1
2
-
3
7
= 
7−6
14
= 
1
14
OBS: Note que existem outras escolhas para as constantes c1 e c2, mas o 
fato importante é que a escolha existe
Notação Θ: Exemplo 2
 Usando a definição formal de Θ prove que 6n3 ≠ Θ(n2).
Resposta !!!!
c1n
2 ≤ 6n3 ≤ c2n
2

c1n
2
𝑛2
≤ 
6n3
𝑛2
≤ 
c2n
2
𝑛2
 c1 ≤ 6n ≤ c2
 n ≤ c2/6 ????
Não é válido para um valor de n arbitrariamente grande, pois c2 é constante
Prof. Rodrigo Freitas Silva / UFES 23
Notação O: Exemplos
o Escreva as seguintes funções em notação O 
(Mostre o limite assintótico restrito)
1. f(n) = 100n
2. f(n) = 2n3 + 100n
3. Mostre que f(n) = n1.5 está em O(n2)
4. f(n) = (n+1)2.
5. 302
6. Seja f(n) = n e g(n) = n2. Mostre que g(n) não é O(n) !!!!
Prof. Rodrigo Freitas Silva / UFES 24
Notação O: Resolução dos Exemplos
1. Seja f(n) = 100n
Logo f(n) é O(n). Suponha: n0 = 1 e c = 100, já que
0 ≤ f(n) ≤ cg(n)
100n ≤ c n para n ≥ 1 e c = 100
2. Seja f(n) = 2n3 + 100n
Logo f(n) é O(n3). Suponha: n0 = 100 e c = 3, já que
2n3 + 100n ≤ 2n3 + n * n * n = 3n3 para n ≥ 100
3. Mostre que f(n) = n1.5 está em O(n2)
Suponha: n0 = 1 e c =1. De fato n1.5 ≤ n0.5n1.5 = n2
Prof. Rodrigo Freitas Silva / UFES 25
Notação O: Resolução dos Exemplos
4. Seja f(n) = (n+1)2
Logo f(n) é O(n2), para n0 = 1 e c = 4, já que
(n+1) 2 ≤ 4n2 para n ≥ 1
5. Seja f(n) = 302
Logo, f(n) = O(1), quando n0 = 1 e c = 302, já que
302 ≤ 302 * 1 para n ≥ 1
6. Seja f(n) = n e g(n) = n2. Mostre que g(n) não é O(n)
o Sabemos que f(n) é O(n2), pois para n ≥ 0, n ≤ n2
o Suponha que existam constantes c e n0 tais que para todo n ≥ n0, n
2 ≤ cn
Assim, c ≥ n para qualquer n ≥ n0. No entanto, não existe uma constante c que 
possa ser maior ou igual a n para todo n
Prof. Rodrigo Freitas Silva / UFES 26
Notação O : mais um exemplo
o Mostre através da definição que g(n) = 3n3 +2n2 +n é O(n3)
o Suponha: n0 = 1 e c =6
Assim, basta mostrar que 3n3 +2n2 +n ≤ 6n3, para n > 0, pois:
3n3 +2n2 +n ≤ 3n3 +2n3 +n3 ≤ 6n3
o OBS: A função g(n) = 3n3 +2n2 +n é também O(n4), entretanto esta 
afirmação é mais fraca do que dizer que g(n) é O(n3)
Prof. Rodrigo Freitas Silva / UFES 27
Notação O: mais exemplos
1) f (n) = n2 – 1  f(n) = O(n2)
2) f (n) = n2 – 1  f(n) = O(n3)
3) f (n) = 403  f(n) = O(1)
4) f (n) = 5 + 2log n + 3log2n  f(n) = O(log2n )
5) f (n) = 5 + 2log n + 3log2n  f(n) = O(n )
6) f (n) = 3n + 5log n + 2  f(n) = O(n )
7) f (n) = 2 * 2n + 5n10  f(n) = O(2n )
Prof. Rodrigo Freitas Silva / UFES 28
Notação O: Propriedades
o f(n) = O(f(n))
o c * O(f(n)) = O(f(n)) sendo c = constante
o O(f(n))+O(f(n)) = O(f(n))
o O(O(f(n)) = O(f(n))
o O(f(n))+O(g(n)) = O(max(f(n); g(n)))
o O(f(n))O(g(n)) = O(f(n)g(n))
o f(n)O(g(n)) = O(f(n)g(n))
Prof. Rodrigo Freitas Silva / UFES 29
Operações com a notação O: Exemplos
1) O produto de [lg n+k +O(1/n)] por [n+O(√n)] é ? 
o Resposta:
= n lg n + lg n (O(√n)) + kn + k O(√n) + n O(1/n) + O(1/n) O(√n) =
= n lg n + O(lg n √n) + kn + O(√n) + O(n * 1/n) + O(1/n * √n) =
= n lg n + kn + O(max(lg n √n; √n; 1; 1/n * √n)) =
= n (lg n + k) + O(lg n √n) 
Atenção às propriedades utilizadas:
o c x O(f(n)) = O(f(n)) sendo c = constante
o O(f(n))+O(g(n)) = O(max(f(n); g(n)))
o O(f(n))O(g(n)) = O(f(n)g(n))
o f(n)O(g(n)) = O(f(n)g(n))
Prof. Rodrigo Freitas Silva / UFES 30
Notação Ω: Exemplos
o Mostrar que f(n) = 3n3 + 2n2 é Ω(n3):
Basta supor c = 1, e então: 3n3 +2n2 ≥ c n3 para todo n > 0
o Mostrar que f(n) = n3 + 100n é Ω(n3): 
Basta supor c = 1, e então: n3 + 100n ≥ c n3 para todo n > 0
Definição de Ω:
Prof. Rodrigo Freitas Silva / UFES 31
Notação Ω: Exercícios
1) Mostrar que f(n) = n2 - 2n é Ω(n2).
2) Mostrar que f(n) = n log n é Ω(n).
3) Mostrar que f(n) = 100 n não está em Ω(n2).
Prof. Rodrigo Freitas Silva / UFES 32
Notação Ω: Resolução dos Exercícios
1. Mostrar que f(n) = n2 - 2n é Ω(n2).
De fato n2 - 2n ≥ ½ n2 para todo n ≥ 4 e c = ½ , pois:
n2 - 2n ≥ n2 - ½ n2 = ½ n2 para todo n ≥ 4
2. Mostrar que f(n) = n lg n é Ω(n).
De fato para c = 1 e todo n ≥ 2 tem-se lg n ≥ 1 e portanto (n lg n ≥ n)
3. Mostrar que f(n) = 100 n não está em Ω(n2).
100n ≥ c*n2  100 ≥ c*n
Logo, percebemos que 100 não é maior que n para n suficientemente grande
Prof. Rodrigo Freitas Silva / UFES 33
POSCOMP 2007
o Observe as funções representadas no gráfico abaixo e assinale a alternativa 
FALSA sobre o crescimento assintótico dessas funções.
A. f(n) = O(h(n)) e i(n) = Ω(g(n)) D. g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
B. f(n) = Θ(h(n)) e i(n) = Ω(h(n)) E. h(n) = Ω(i(n)), logo, i(n) = O(h(n))
C. g(n) = O(i(n)) e h(n) = Ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 34
POSCOMP 2007
o Observe as funções representadas no gráfico abaixo e assinale a alternativa 
FALSA sobre o crescimento assintótico dessas funções.
A. f(n) = O(h(n)) e i(n) = Ω(g(n)) D. g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
B. f(n) = Θ(h(n)) e i(n) = Ω(h(n)) E. h(n) = Ω(i(n)), logo, i(n) = O(h(n))
C. g(n) = O(i(n)) e h(n) = Ω(g(n))
Prof. Rodrigo Freitas Silva / UFES 35
POSCOMP 2003
o Quais das seguintes igualdades são verdadeiras?
I. n2 = O(n3)
II. 2*n + 1 = O(n2)
III. n3 = O(n2)
IV. 3*n + 5*n log n = O(n)
V. log n + 𝑛= O(n)
A. Somente I e II
B. Somente II, III e IV
C. Somente III, IV e V
D. Somente I, II e V
E. Somente I, III e IV
Prof. Rodrigo Freitas Silva / UFES 36
POSCOMP 2003
o Quais das seguintes igualdades são verdadeiras?
I. n2 = O(n3)
II. 2*n + 1 = O(n2)
III. n3 = O(n2)
IV. 3*n + 5*n log n = O(n)
V. log n + 𝑛= O(n)
A. SomenteI e II
B. Somente II, III e IV
C. Somente III, IV e V
D. Somente I, II e V
E. Somente I, III e IV
Prof. Rodrigo Freitas Silva / UFES 37
Notação assintótica em funções
o Exercícios:
1) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a 
definição básica da notação Θ, prove que max(f(n), g(n)) = Θ(f(n) + g(n))
2) Mostre que, para quaisquer constantes reais a e b, onde b > 0, 
(n + a)b = Θ(nb)
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
4) f(n) = O(g(n)) implica g(n) = O(f(n)) ????
Prof. Rodrigo Freitas Silva / UFES 38
Notação assintótica em funções
o Exercícios - Resolução
1) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a definição 
básica da notação Θ, prove que max(f(n), g(n)) = Θ(f(n) + g(n)).
R: Mostrar que max(f(n), g(n)) = Θ(f(n) + g(n)) significa dizer que existem 
constantes positivas c1, c2 e n0 tal que:
0 ≤ c1(f(n) + g(n)) ≤ max(f(n), g(n)) ≤ c2(f(n) + g(n)) para todo n ≥ n0
o Se escolhermos c2 = 1, a terceira inequação é claramente satisfeita, já que a maior das 
duas funções deve ser menor que sua soma.
o Poderíamos escolher c1 como ½, já que a maior das funções é sempre maior do que a 
média entre f(n) e g(n) Prof. Rodrigo Freitas Silva / UFES 39
o Exercícios - Resolução
2) Mostre que, para quaisquer constantes reais a e b, onde b > 0, (n + a)b = Θ(nb)
R: Precisaremos achar as constantes positivas c1, c2 e n0 > 0, tal que:
0 ≤ c1n
b ≤ (n + a)b ≤ c2n
b para todo n ≥ n0
Note que: n + a ≤ n + |a| ≤ 2n quando |a| ≤ n
n + a ≥ n - |a| ≥ ½ n quando |a| ≤ ½ n  n ≥ 2|a|
Logo:
0 ≤ ½ n ≤ n + a ≤ 2n
 0 ≤ (½ n)b ≤ (n + a)b ≤ (2n)b
 0 ≤ (½)b nb ≤ (n + a)b ≤ 2bnb
Assim, c1 = (1/2)b, c2 = 2b, e n0 = 2|a| satisfaz a definição.
Notação assintótica em funções
Prof. Rodrigo Freitas Silva / UFES 40
Notação assintótica em funções
o Exercícios - Resolução
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
R: Para mostrar que 2n+1 = O(2n) devemos achar as constantes 
c, n0 > 0 que:
0 ≤ 2n+1 ≤ c (2n) para todo n ≥ n0
Já que 2n+1 = 2(2n) para todo n, a definição é satisfeita com c = 2 e n0 = 1 
Prof. Rodrigo Freitas Silva / UFES 41
Notação assintótica em funções
o Exercícios - Resolução
3) É verdade que 2n+1 = O(2n) ??? É verdade que 22n = O(2n) ???
R: Vamos assumir que existam constantes c, n0 > 0 tais que:
0 ≤ 22n ≤ c (2n) para todo n ≥ n0
Logo 22n = (2n)2 = 2n(2n) ≤ c (2n)  2n ≤ c
Mas nenhuma constante é maior que todos 2n
Assim, 22n ≠ O(2n) 
Prof. Rodrigo Freitas Silva / UFES 42
Notação assintótica em funções
o Exercícios - Resolução
4) f(n) = O(g(n)) implica g(n) = O(f(n)) ????
o Não, f(n) = O(g(n)) não implica g(n) = O(f(n)).
o Como contra-exemplo tem-se: f(n) = n e g(n) = n2
Logo:
n = O(n2) mas n2 ≠ O(n)
Prof. Rodrigo Freitas Silva / UFES 43
POSCOMP 2002
Quais das seguintes afirmações sobre crescimento assintótico de 
funções não é verdadeira?
a) 2n2 + 3n + 1 = O(n2)
b) Se f(n) = O(g(n)) então g(n) = O(f(n))
c) log n2 = O(log n)
d) Se f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n)) 
e) 2n+1 = O(2n)
Prof. Rodrigo Freitas Silva / UFES 44
POSCOMP 2002
Quais das seguintes afirmações sobre crescimento assintótico de 
funções não é verdadeira?
a) 2n2 + 3n + 1 = O(n2)
b) Se f(n) = O(g(n)) então g(n) = O(f(n))
c) log n2 = O(log n)
d) Se f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n)) 
e) 2n+1 = O(2n)
Prof. Rodrigo Freitas Silva / UFES 45
Exercício 1
Dois algoritmos A e B possuem complexidade n7 e 3n, respectivamente. 
Você utilizaria o algoritmo B ao invés do A? Em qual caso? 
Exemplifique.
Resposta: Sim. Apesar do algoritmo ser exponencial, quando o 
valor de n é pequeno, esta função produz um tempo de complexidade 
menor do que a função do algoritmo A. Por exemplo para valores de n
de 2 a 15 
Prof. Rodrigo Freitas Silva / UFES 46
Bibliografias utilizadas
1. Aho, A. V.; Hopcroft, J. E.; Ullman, J. D.; The Design and Analysis of 
Computer Algorithms, 1ed, Ed. Addison Wesley, 1974
2. T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein; Algoritmos: Teoria e 
Prática, ed.2, Campus, 2002. 
3. Jayme Luiz Swarcfiter, Lilian Markenzon, Estruturas de Dados e Seus
Algoritmos, 2a edition
4. Nivio Ziviani , Projeto De Algoritmos, 2º ed. , 2004
5. Papadimitriou, C. H.; Computational Complexity. 1ed, Ed. Addison Wesley, 
1994. 
6. Garey, M. R.; Johnson, D. S.; Computers and intractability: A guide to the 
theory of NP-completeness. Ed. Freeman, 1979. 
7. Toscani, L. V.; Veloso, P. A. S.; Complexidade de Algoritmos, 2ed, Ed. 
Bookman, 2008. 
Prof. Rodrigo Freitas Silva / UFES 47