Faculdade Campo Limpo Paulista
Mestrado em Ciência da Computação
Complexidade de Algoritmos – Avaliação 2
1. (2,0): Resolva a seguinte relação de recorrência, para k igual a uma constante.
T (n) = T (n – 1) + k
T (1) = k
SOLUÇÃO
Pelo método iterativo progressivo.
T (1) = k
T (2) = T(1) + k = k + k = 2 k
T (3) = T(2) + k = 2 k + k = 3 k
T (4) = T(1) + k = 3 k + k = 4 k
...
T (n) = k n = O (n)
2. (2,0): Mostre, por indução, que a relação de recorrência a seguir tem como resultado
2n – 1.
T (n) = 2 T (n – 1) + 1
T (1) = 1
SOLUÇÃO
i) Base
T (1) = 1. Pela fórmula, 21 – 1 = 1. A fórmula é verdadeira para a base.
ii) Hipótese de indução
T (n – 1) = 2n - 1 – 1.
iii) Relação entre T (n) e T (n – 1)
É dada pela própria relação de recorrência, ou seja,
T (n) = 2 T (n – 1) + 1.
iv) Provando que T(n – 1) ⇒ T(n)
T (n) = 2 T (n – 1) + 1
T (n) = 2 (2n - 1 – 1) + 1
T (n) = 2n – 2 + 1
T (n) = 2n – 1
3. (2,0): Prove, por indução, que a soma das diagonais de um polígono convexo de n
lados (n ≥ 3) é igual a S(n) = n (n – 3) / 2. Um polígono é convexo quando os
segmentos de reta que unem dois quaisquer de seus vértices ficam inscritos no
polígono.
SOLUÇÃO
i) Base.
Para n = 3 temos um triângulo, ou seja, zero diagonal.
3
2
1
Pela fórmula S(n) = n (n – 3) / 2 = 3 (3 – 3) / 2 = 0. A fórmula é verdadeira para a base.
ii) Hipótese de indução.
S (n – 1) = (n – 1) (n – 4) / 2 , n ≥ 4.
iii) Relação entre a soma das diagonais de um polígono convexo de n lados e tal soma em um
polígono convexo de n – 1 lados.
n - 3 diagonais devidas
a este vértice
...
...
1 nova diagonal
polígono com n - 1 lados tem
S( n - 1) diagonais
Pela ilustração acima, infere-se que S(n) = S(n – 1) + n - 2.
iv) Prova do fato de S(n – 1) ser verdadeira implica que S(n) é verdadeira.
S(n) = S(n – 1) + n – 2.
S(n) = (n – 1) (n – 4) / 2 + n – 2.
S(n) = (n2 – 5n + 4 + 2n – 4) / 2.
S(n) = (n2 – 3n) / 2.
S(n) = n (n – 3) / 2.
polígono com n lados
S(n ) = S(n - 1) + n - 2 diagonais
4. (2,0): Calcule a complexidade do algoritmo a seguir. Dê o resultado do seu cálculo
em função do tamanho da entrada n = f – i + 1.
Algoritmo S(i, f)
Entrada: i e f, naturais, i ≤ f.
Saída: a soma dos naturais no intervalo fechado de i até f.
{
se (i = f)
retornar i
senão
{
m := (i + f) / 2 ;
retornar S(i, m) + S (m + 1, f)
}
}
SOLUÇÃO
T (n)
T (1)
Algoritmo S(i, f)
Entrada: i e f, naturais, i ≤ f.
Saída: a soma dos naturais no intervalo fechado de i até f.
{
se (i = f)
retornar i
senão
tempo para fazer 1 soma
{
m := (i + f) / 2 ;
retornar S(i, m) + S (m + 1, f)
}
}
T (n/2)
T (n/2)
T (n) = 2 T (n/2) + 1
T (1) = 1
Esta relação de recorrência é do tipo “dividir para conquistar”, T(n) = aT(n/b) + cnk, cuja
solução está tabelada.
Neste caso a = 2 ( a ≥ 1, OK ), b = 2 ( b ≥ 2, OK ), c = 1 e k = 0 (c e k constantes, OK).
Como a = 2 > bk = 20 = 1, então
T (n) = O ( nk ) = O ( n0) = O ( n ).
5. (2,0): Aplicando a técnica indutiva de design de algoritmos, escreva um algoritmo
que avalie o valor de uma expressão, em notação prefixa (notação polonesa),
constituída por números e pelos operadores + e *. A tabela abaixo inclui exemplos
de expressões na notação prefixa e sua correspondente interpretação na notação
convencional infixa.
Tabela 1. Exemplos de expressões em notação prefixa e correspondente expressão na notação
convencional infixa.
Expressão prefixa
1
+12
+1*23
*+123
*+12+34
Corresponde à expressão em notação infixa
1
1+2
1+2*3
(1 + 2) * 3
(1 + 2) * (3 + 4)
Sugestão de solução
Assuma que a expressão a ser avaliada foi previamente atribuída ao sistema e que os
elementos dela (operandos e operadores) podem ser obtidos um a um, em sequencia,
por meio do algoritmo Próximo. Assim, por exemplo, se a expressão ‘+ 1 2’ for atribuída
ao sistema, então as chamadas do algoritmo Próximo retornarão:
• s := Próximo; // s receberá o símbolo +;
• s := Próximo; // s receberá o símbolo 1;
• s := Próximo; // s receberá o símbolo 2;
• s := Próximo; // s receberá o símbolo #, indicando o fim da expressão.
Utilize:
i) Interface: use a seguinte interface, sem parâmetros.
Avaliar
ii) Significado:
Retorna o valor de uma subexpressão completa, escrita na notação prefixa.
SOLUÇÃO
iii) Redução
Uma subexpressão completa possui uma das seguintes formas:
• número;
• + número número;
• * número número;
Comandos
s := Próximo;
se ( s = + ) então
{
v1 := Avaliar; v1 := Avaliar;
retornar v1 + v2
}
senão
se ( s = * ) então
{
v1 := Avaliar; v1 := Avaliar;
retornar v1 * v2
}
senão
retornar s
iv) Base
As reduções consomem os símbolos da expressão, conduzindo o algoritmo Próximo a
retornar o símbolo #. A base, portanto, será caracterizada pelo retorno deste símbolo
pelo algoritmo Próximo.
A subexpressão a ser avaliada não existe. Como temos que retornar um certo valor
(significado estabelecido) então parece razoável retornar o valor zero.
Comandos
retornar 0.
Algoritmo Avaliar
{
s := Próximo;
se (s = #)
retornar 0
senão
{
se ( s = + ) então
{
v1 := Avaliar; v1 := Avaliar;
retornar v1 + v2
}
senão
se ( s = * ) então
{
v1 := Avaliar; v1 := Avaliar;
retornar v1 * v2
}
senão // s é um número.
retornar s
}
}
6. (2,0): (opcional1): prove que é T(n) = O (n log n), onde:
T ( n) = n − 1 +
2 n −1
∑ T (i) para n ≥ 2
n i =1
T (1) = 1
SOLUÇÃO
Precisamos mostrar que ∃ c > 0 e N | T (n) ≤ c n log n ∀ n ≥ N.
Como T (1) = 1 > c 1 log 1 = 0, antes de começarmos a prova, reescrevemos que
provaremos que T (n) = O (n log n) para n ≥ 2. Temos assim uma restrição para N,
ou seja, N ≥ 2.
i) Base
T (2) = 2 – 1 + (2/2) T(1) = 1 + (2/2) 1 = 2.
Para satisfazer a base, precisamos que T(2) ≤ c 2 log 2. Ou seja,
2 ≤ 2 c,
c ≥ 1 (basta c ser maior ou igual a 1 para satisfazer a esta base. Esta é a primeira
restrição para o valor de c).
ii) Redução
É dada pela expressão geral da relação de recorrência, para a qual:
2 n −1
T (n) = n − 1 + ∑ T (i ) .
n i =1
iii) Hipóteses de indução
Como T (n) reduz para T(1), T(2), ..., T(n - 1) então formulamos o conjunto de
hipóteses:
T (i) ≤ c i log i, para i → 2, 3, 4, ..., n – 1.
iv) Prova de que o fato de T(i) ≤ c i log i, i → 2, 3, 4, ..., n – 1, implica que
T(n) ≤ c n log n.
T ( n) = n − 1 +
2 n −1
∑ T (i)
n i =1
2 n −1
∑ ci log i (usamos a hipótese de indução)
n i =1
2c n −1
T (n) ≤ n − 1 + ∑ i log i (tiramos a constante c para fora do somatório)
n i =1
T (n ) ≤ n − 1 +
1
Poderá ser utilizada para substituir algum dos exercícios anteriores.
2c 1 2
1
( n log n − n 2 − 3) (o resultado do somatório será mostrado depois)
n 2
4
1
6c
(aplicamos a distributiva em relação a 2c/n)
T (n) ≤ n − 1 + cn log n − cn −
2
n
1
T (n) ≤ n + cn log n − cn (eliminamos -1 e -6c/n)
2
2n − cn
(rearranjamos a ordem dos termos e agrupamos n e – (1/2)cn).
T (n) ≤ cn log n +
2
T ( n) ≤ n − 1 +
Como 2n – cn ≤ 0 para c ≥ 2 (segunda restrição para o valor de c),
T (n) ≤ cn log n , para, digamos c = 2 e N = 2.
_________________
Mostrando que
n −1
1
∑ i log i ≤ 2 n
i =1
n −1
n
i =1
2
2
1
log n − n 2 − 3 .
4
∑ i log i ≤ ∫ x log xdx .
Vamos resolver a integral pela regra da cadeia, onde ∫ udv = uv − ∫ vdu .
Sejam,
u = log x e dv = xdx.
Então,
du 1
1
= , ou seja, du = dx e
dx x
x
1 2
∫ dv = ∫ xdx , ou seja, v = 2 x . Logo:
1 2
1 21
∫ x log xdx = 2 x log x − ∫ 2 x x dx ,
1 2
1 2
∫ x log xdx = 2 x log x − 4 x .
Voltando à integral com limites definidos
n
n
1 2
1 2
1 2
1 2
1 2
1 2
∫2 x log xdx = [ 2 x log x − 4 x ] = 2 n log n − 4 n − 2 log 2 − 1 = 2 n log n − 4 n − 3.
2
Logo,
n −1
1
∑ i log i ≤ 2 n
i =1
2
1
log n − n 2 − 3 .
4