PAA+ +2019 01+ +parte+03

Prévia do material em texto

Projeto e Análise de Algoritmos
3ª parte
Prof. Jobson Massollar
jobson.silva@uva.br
Projeto e Análise de Algoritmos2
Estruturas de Controle
➢ Conforme visto anteriormente, para calcular a função f(n) de tempo
de um algoritmo devemos contar o números de passos elementares
do mesmo:
int soma(int n) {
int i;
int acumulador = 0;
for(i = 0; i < n; i++)
acumulador += i;
return acumulador;
}
Projeto e Análise de Algoritmos3
Estruturas de Controle
➢ Conforme visto anteriormente, para calcular a função f(n) de tempo
de um algoritmo devemos contar o números de passos elementares
do mesmo:
int soma(int n) {
int i;
int acumulador = 0;
for(i = 0; i < n; i++)
acumulador += i;
return acumulador;
}
➢ f(n) = 1 + 1 + (n+1) + 2n + 1 = 3n + 4 → O(n)
1
1
1 n+1
2n
Projeto e Análise de Algoritmos4
Estruturas de Controle
➢ Para o cálculo da complexidade não existem regras rígidas que
possam ser aplicadas a qualquer algoritmo, pois cada caso deve ser
avaliado em suas particularidades.
➢ No entanto, as estruturas de controle clássicas da programação
estruturada permitem uma estimativa típica de cada uma.
➢ Assim, os algoritmos construídos a partir de combinações dessas
estruturas podem ter sua complexidade mais facilmente
estabelecida.
Projeto e Análise de Algoritmos5
Estruturas de Controle
1. Comando simples: tem um tempo constante de execução, logo é
considerado O(1).
2. Sequência de comandos: em uma sequência, cada comando é da
ordem de O(1). Assim, a sequência é da ordem de (vide
propriedade c):
O(1) + O(1) + O(1) + ... + O(1) = O(1)
3. Comandos de seleção: deve-se calcular a complexidade de cada
uma das alternativa e usar a maior. Assim:
a) A complexidade de um IF-THEN-ELSE é a complexidade do bloco
THEN ou ELSE, a que for maior.
b) A complexidade de um SWITCH é a complexidade de um dos blocos
CASE, a que for maior.
Projeto e Análise de Algoritmos6
Estruturas de Controle
4. Comandos de repetição:
a) Se o número de iterações independe do tamanho da entrada n, então
a complexidade da repetição é a complexidade do bloco repetido (vide
propriedade b).
Exemplo:
for (int i = 1; i <= 10; i++) {
x = x + y;
printf(“%d\n”, x);
} O(1), pois o bloco 
do FOR é O(1)
Projeto e Análise de Algoritmos7
Estruturas de Controle
4. Comandos de repetição:
b) Se o número de iterações depende do tamanho da entrada n, então a
complexidade da repetição é a complexidade do bloco repetido
multiplicado pela função que descreve o número de iterações.
Exemplo 1:
for (int i = 1; i <= k * n; i++) {
x = x + i;
printf(“%d\n”, x);
}
Logo, a complexidade é (vide propriedade d):
k * n * O(1) = O(k * n * 1) = O(n)
O(1)
Número de 
iterações: k * n
Projeto e Análise de Algoritmos8
Estruturas de Controle
4. Comandos de repetição:
b) Se o número de iterações depende do tamanho da entrada n, então a
complexidade da repetição é a complexidade do bloco repetido
multiplicado pela função que descreve o número de iterações.
Exemplo 2:
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
x = x + i + j;
printf(“%d\n”, x);
}
Logo, a complexidade é (vide propriedade d):
n * n * O(1) = O(n * n * 1) = O(n2)
O(1)
Número de iterações: n
Número de iterações: n
Projeto e Análise de Algoritmos9
Estruturas de Controle
4. Comandos de repetição:
b) Se o número de iterações depende do tamanho da entrada n, então a
complexidade da repetição é a complexidade do bloco repetido
multiplicado pela função que descreve o número de iterações.
Exemplo 3:
limite = 1;
while (limite <= n) {
printf(“%d\n”, limite);
limite = limite * 2;
}
Como o limite dobra a cada iteração, depois de k iterações teremos:
limite = 2k ou k = log2limite
Como o valor máximo de limite é n, então o número de iterações é:
log2n
Assim, a complexidade da repetição é: log2n . O(1) = O(log(n))
O(1)
Projeto e Análise de Algoritmos10
Estruturas de Controle
4. Comandos de repetição:
b) Se o número de iterações depende do tamanho da entrada n, então a
complexidade da repetição é a complexidade do bloco repetido
multiplicado pela função que descreve o número de iterações.
Exemplo 4:
limite = n;
while (limite != 0) {
printf(“%d\n”, limite);
limite = limite / 2;
}
O limite cai à metade a cada iteração, logo teremos k iterações onde:
k = log2n
Assim, a complexidade da repetição é: log2n . O(1) = O(log(n))
O(1)
Projeto e Análise de Algoritmos11
Estruturas de Controle
5. Chamadas de funções/procedimentos: para calcular a
complexidade de um programa com várias funções, determina-se
primeiro a complexidade de cada uma das funções. Desta forma,
cada uma das funções é vista como uma instrução com a
complexidade que foi calculada.
Exemplo:
int main() {
f1();
f2();
f3();
}
Logo, a complexidade é da função main é (vide propriedade e):
O(n) + O(log n) + O(n2) = O(max(n, log n, n2)) = O(n2)
O(n)
O(log n)
O(n2)
Projeto e Análise de Algoritmos12
Estruturas de Controle
➢ Algumas fórmulas úteis:
෍
𝑖=1
𝑛
𝑖 =
𝑛(𝑛 + 1)
2
෍
𝑖=1
𝑛
𝑖 − 1 =
𝑛(𝑛 − 1)
2
෍
𝑖=1
𝑛
𝑖 + 𝑘 =
(𝑛 + 𝑘)(𝑛 + 𝑘 + 1)
2
෍
𝑖=0
𝑛
2𝑖 = 2𝑛+1 − 1
෍
𝑖=0
𝑛
1
2𝑖
= 2 −
1
2𝑛
෍
𝑖=0
𝑛
𝑎𝑖 =
𝑎𝑛+1 − 1
𝑎 − 1
(a ≠ 1)
෍
𝑖=1
𝑛
𝑖2 =
𝑛(𝑛 + 1)(2𝑛 + 1)
6
Projeto e Análise de Algoritmos13
Exercícios
➢ Exemplo 1: somatório de 1..n
int soma(int n) {
int i;
int acumulador = 0;
for(i = 1; i <= n; i++)
acumulador += i;
return acumulador;
}
Projeto e Análise de Algoritmos14
Exercícios
➢ Exemplo 1: somatório de 1..n
int soma(int n) {
int i;
int acumulador = 0;
for(i = 1; i <= n; i++)
acumulador += i;
return acumulador;
}
n repetições
→ O(1)
→ O(1)
→ O(1)
𝑂 1 + 𝑂 𝑛 + 𝑂 1 = 𝑂 max 1, 𝑛, 1 = 𝑂(𝑛)
Projeto e Análise de Algoritmos15
Exercícios
➢ Exemplo 2: inversão de um vetor
void inverte(int v[], int n) {
for(i = 0; i < n/2; i++) {
int aux = v[i];
v[i] = v[n-i-1];
v[n-i-1] = aux;
}
}
Projeto e Análise de Algoritmos16
Exercícios
➢ Exemplo 2: inversão de um vetor
void inverte(int v[], int n) {
for(i = 0; i < n/2; i++) {
int aux = v[i];
v[i] = v[n-i-1];
v[n-i-1] = aux;
}
}
3 passos: O(1)
n/2 repetições
𝑛
2
. 𝑂 1 = 𝑂
𝑛
2
. 1 = 𝑂
𝑛
2
= 𝑂(𝑛)
Projeto e Análise de Algoritmos17
Exercícios
➢ Exemplo 3: xn
long potencia(int x, int n) {
long p = 1;
for(int i = 0; i < n; i++)
p *= x;
return p;
}
Projeto e Análise de Algoritmos18
Exercícios
➢ Exemplo 3: xn
long potencia(int x, int n) {
long p = 1;
for(int i = 0; i < n; i++)
p *= x;
return p;
}
n repetições
→ O(1)
→ O(1)
→ O(1)
𝑂 1 + 𝑛.𝑂 1 + 𝑂 1 = 𝑂 1 + 𝑂 𝑛. 1 + 𝑂 1 = 𝑂 max 1, 𝑛, 1 = 𝑂(𝑛)
Projeto e Análise de Algoritmos19
Exercícios
➢ Exemplo 4:
void eureka(int n) {
int i, j;
int a = 0;
for(i = 0; i < n; i++)
for(j = n; j > i; j--)
a += i + j;
printf(“%d\n”, a);
}
Projeto e Análise de Algoritmos20
Exercícios
➢ Exemplo 4:
void eureka(int n) {
int i, j;
int a = 0;
for(i = 0; i < n; i++)
for(j = n; j > i; j--)
a += i + j;
printf(“%d\n”, a);
}
i = 0
j = n..1 (n vezes)
i = 1
j = n..2 (n-1 vezes)
i = 2
j = n..3 (n-2 vezes)
i = 3
j = n..4 (n-3 vezes)
i = n-1
j = n..n-1+1 (1 vez)
→ O(1)
𝑛 + 𝑛 − 1 + 𝑛 − 2 +⋯+ 2 + 1 =
𝑛 𝑛 + 1
2
=
𝑛2 + 𝑛
2
= 𝑂(𝑛2)
෍
𝑖=1
𝑛
𝑖 =
𝑛(𝑛 + 1)
2
Projeto e Análise de Algoritmos21
Exercícios
➢ Exemplo 5: validação de número primo
bool primo(int n) {
if(n == 2)
return true;
for(i = 2; i < n/2; i++)
if (n % i == 0)
return false;
return true;
}
Projeto e Análise de Algoritmos22
Exercícios
➢ Exemplo 5: validação de número primo
bool primo(int n) {
if (n == 2)
return true;
for(i = 2; i < n/2; i++)
if (n % i == 0)
return false;
return true;
}
n/2-2 repetições
→ O(1)
𝑛
2
− 2 . 𝑂 1 = 𝑂
𝑛
2
− 2 = 𝑂(𝑛)
Projeto e Análise de Algoritmos23
Exercícios
➢ Exemplo 6: ordenação por seleção
void ordena(int v[], int n) {
int i, j, min;
for(i = 0; i < n-1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (v[j] < v[min])
min = j;
if (min != i) {
int temp = v[min];
v[min] = v[i];
v[i] = temp;
}
}
}
Projeto e Análise de Algoritmos24
Exercícios
➢ Exemplo 6: ordenação por seleção
void ordena(int v[], int n) {
int i, j, min;
for(i = 0; i < n-1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (v[j] < v[min])
min = j;
if (min != i) {
int temp = v[min];
v[min] = v[i];
v[i] = temp;
}
}
}
n-1 repetições
n-1, n-2, n-3,...,2, 1 repetições
O(1)
O(1)
𝑛 − 1 + 𝑛 − 2 + 𝑛 − 3 +⋯+ 2 + 1 =
𝑛(𝑛 − 1)
2
=
𝑛2 − 𝑛
2
= 𝑂(𝑛2)
෍
𝑖=1
𝑛
𝑖 − 1 =
𝑛(𝑛 − 1)
2
Projeto e Análise de Algoritmos25
Exercícios
➢ Exemplo 7: multiplicação de matrizes
// Matrizes A, B e C são variáveis globais
void mult(int n) {
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++) {
c[i][j] = 0;
for(k = n-1; k >= 0; k--)
c[i][j] += a[i][k] * b[k][j];
}
}
Projeto e Análise de Algoritmos26
Exercícios
➢ Exemplo 7: multiplicação de matrizes
// Matrizes A, B e C são variáveis globais
void mult(int n) {
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++) {
c[i][j] = 0;
for(k = n-1; k >= 0; k--)
c[i][j] += a[i][k] * b[k][j];
}
}
n repetições
n repetições
n repetições
→ O(1)
𝑛. 𝑛. 𝑛. 𝑂 1 = 𝑂 𝑛3. 1 = 𝑂(𝑛3)
Projeto e Análise de Algoritmos27
Exercícios
➢ Exemplo 8:
void misterio(int n) {
int i, j, x=0, y=0;
for(i = 1; i <= n; i++) {
for(j = i; j <= n; j++) {
x++;
for(j = 1; j < i; j++)
y++;
}
}
Projeto e Análise de Algoritmos28
Exercícios
➢ Exemplo 8:
void misterio(int n) {
int i, j, x=0, y=0;
for(i = 1; i <= n; i++) {
for(j = i; j <= n; j++)
x++;
for(j = 1; j < i; j++)
y++;
}
}
n repetições
n, n-1, n-2, ..., 3, 2, 1 repetições
0, 1, 2, 3, ..., n-2, n-1 repetições
෍
𝑖=1
𝑛
𝑖 =
𝑛(𝑛 + 1)
2
෍
𝑖=1
𝑛
𝑖 − 1 =
𝑛(𝑛 − 1)
2
𝑂
𝑛(𝑛 + 1)
2
+ O
𝑛(𝑛 − 1)
2
= O 𝑚𝑎𝑥
𝑛(𝑛 + 1)
2
,
𝑛(𝑛 − 1)
2
= 𝑂(𝑛2)
Projeto e Análise de Algoritmos29
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
1ª iteração:
ini = 0
fim = n-1
meio = (n-1)/2
Espaço de busca: fim – ini + 1 = (n-1) - 0 + 1 = n
Ou seja n elementos.
Projeto e Análise de Algoritmos30
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
2ª iteração:
ini = 0
fim = meio–1 = (n-1)/2-1
meio = ((n-1)/2-1)/2
OU
ini = meio+1 = (n-1)/2+1
fim = n-1
meio = (((n-1)/2+1) + (n-1))/2
Espaço de busca: (n-1)/2 - 1 - 0 + 1 = (n-1)/2
Ou seja, n/2 elementos.
Projeto e Análise de Algoritmos31
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
3ª iteração:
ini = 0
fim = meio-1 = (((n-1)/2-1)/2) – 1
meio = ((((n-1)/2-1)/2) – 1) / 2
OU
ini = meio+1 = (((n-1)/2+1) + (n-1))/2 + 1
fim = n-1
Meio = (((((n-1)/2+1) + (n-1))/2 + 1) + (n-1)) / 2
Espaço de busca: (((n-1)/2-1)/2) – 1 – 0 + 1 = ((n-1)/2-1)/2 =
= (n-3)/4
Ou seja, n/4 elementos.
Projeto e Análise de Algoritmos32
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
Assim, a cada iteração o espaço de busca é
reduzido à metade.
Na iteração k teremos
𝒏
𝟐𝒌−𝟏
elementos no espaço
de busca.
Iteração Espaço de busca
1 n = n/20
2 n/2 = n/21
3 n/4 = n/22
4 n/8 = n/23
... ...
k n/2k-1
Projeto e Análise de Algoritmos33
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
Pergunta-se: dado um inteiro n > 0, quantas
iterações são necessárias para dividir n à
metade até atingir 1?
𝑛
2𝑘−1
= 1 ֜ 𝑛 = 2𝑘−1 ֜ 𝑙𝑜𝑔2𝑛 = 𝑙𝑜𝑔22
𝑘−1
֜ 𝑙𝑜𝑔2𝑛 = 𝑘 − 1 ֜ 𝑘 = 𝑙𝑜𝑔2𝑛 + 1
Ou seja, log2n + 1 iterações.
Projeto e Análise de Algoritmos34
Exercícios
➢ Exemplo 9: busca binária (buscabin.cpp)
int pesqbin(int v[], int n, int k) {
int meio, ini=0, fim=n-1;
while (ini <= fim) {
meio = (ini + fim) / 2;
if (v[meio] == k)
return meio;
if (k < v[meio])
fim = meio - 1;
else
ini = meio + 1;
}
return -1;
}
O(1)
log2n + 1 repetições
𝑙𝑜𝑔2𝑛 + 1 .𝑂 1 = 𝑂 𝑙𝑜𝑔2𝑛 + 1 = 𝑂(log 𝑛)
Projeto e Análise de Algoritmos35
Recursividade
➢ Todo algoritmo recursivo é composto de:
a) Um ou mais casos-base (situações onde o algoritmo atinge uma
solução trivial).
b) Uma ou mais chamadas recursivas (definição da solução em função
dela mesma).
int fat(int n) {
if (n == 0)
return 1;
return n * fat(n-1);
}
Caso-base
Definição recursiva
Projeto e Análise de Algoritmos36
Recursividade
➢ Analisando a função de tempo f do algoritmo abaixo, temos:
int fat(int n) {
if (n == 0)
return 1;
return n * fat(n-1);
}
Para o caso-base 
temos 2 passos.
𝑓 𝑛 = 2 , 𝑠𝑒 𝑛 = 0
Projeto e Análise de Algoritmos37
Recursividade
➢ Analisando a função de tempo f do algoritmo abaixo, temos:
int fat(int n) {
if (n == 0)
return 1;
return n * fat(n-1);
}
Para a recursão temos 4 passos
mais os passos relativos à 
chamada recursiva.
𝑓 𝑛 = 2 , 𝑠𝑒 𝑛 = 0
𝑓 𝑛 = 𝑓 𝑛 − 1 + 4, 𝑠𝑒 𝑛 > 0
Para calcular a complexidade 
devemos resolver essa equação 
de recorrência!
Projeto e Análise de Algoritmos38
Recursividade
➢ Resolver uma equação de recorrência nem sempre é fácil.
➢ Algumas técnicas:
✓ Método da iteração: expande a recorrência e usa propriedades
algébricas para encontrar e resolver um somatório.
✓ Método da substituição: pressupõe uma solução e usa indução
matemática para verificar se a suposição se aplica.
✓ Método da árvore de recursão: é um método intuitivo que
consiste e desenhar uma árvore cujos nós representam o custo
nos diversos níveis da recursão.
✓ Método mestre: teorema que define como resolver equações de
recorrência que seguem determinados padrões.
Projeto e Análise de Algoritmos39
Recursividade
➢ Aplicando o método da iteração:
f(n) = f(n-1) + 4
f(n) = f(n-2) + 4+ 4
f(n) = f(n-3) + 4 + 4 + 4
f(n) = f(n-4) + 4 + 4 + 4 + 4
f(n) = f(n-5) + 4 + 4 + 4 + 4 + 4
...
f(n) = f(n-k) + 4k
Caso-base é alcançado quando n - k = 0, ou seja, k = n:
f(n) = f(n-n) + 4n
f(n) = 4n + 2 = O(n)
𝑓 𝑛 = 2 , 𝑠𝑒 𝑛 = 0
𝑓 𝑛 = 𝑓 𝑛 − 1 + 4, 𝑠𝑒 𝑛 > 0
O 4 é somado k vezes.
Projeto e Análise de Algoritmos40
Recursividade
➢ Outra forma de resolver:
f(n) = f(n-1) + 4
f(n-1) = f(n-2) + 4
f(n-2) = f(n-3) + 4
f(n-3) = f(n-4) + 4
f(n-4) = f(n-5) + 4
...
f(n-n+1) = f(n-n) + 4
Somando os termos dos lados direito e esquerdo:
f(n) + f(n-1) + f(n-2) + f(n-3) + f(n-4) +...+f(1) = f(n-1) + f(n-2) + f(n-3) + f(n-
4) +...+f(1) + f(0) + 4 + 4 + 4 +...+ 4
f(n) = f(0) + 4n
f(n) = 4n + 2 = O(n)
𝑓 𝑛 = 2 , 𝑠𝑒 𝑛 = 0
𝑓 𝑛 = 𝑓 𝑛 − 1 + 3, 𝑠𝑒 𝑛 > 0
O 4 é somado n vezes.
Projeto e Análise de Algoritmos41
Recursividade
➢ Torre de Hanoi (hanoi.cpp):
void hanoi(int discos, int origem, int destino, int aux) {
if (discos == 1) {
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
return;
}
hanoi(discos-1, origem, aux, destino);
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
hanoi(discos-1, aux, destino, origem);
}
𝑓 𝑛 = 3 , 𝑠𝑒 𝑛 = 1
Projeto e Análise de Algoritmos42
Recursividade
➢ Torre de Hanoi (hanoi.cpp):
void hanoi(int discos, int origem, int destino, int aux) {
if (discos == 1) {
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
return;
}
hanoi(discos-1, origem, aux, destino);
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
hanoi(discos-1, aux, destino, origem);
}
𝑓 𝑛 = 3 , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 2. 𝑓 𝑛 − 1 + 4, 𝑠𝑒 𝑛 > 1
Projeto e Análise de Algoritmos43
Recursividade
➢ Aplicando o método da iteração:
f(n) = 2.f(n-1) + 4
f(n) = 2.(2.f(n-2) + 4) + 4 = 4.f(n-2) + 8 + 4
f(n) = 4.(2.f(n-3) + 4) + 8 + 4 = 8.f(n-3) + 16 + 8 + 4
f(n) = 8.(2.f(n-4) + 4) + 16 + 8 + 4 = 16.f(n-4) + 32 + 16 + 8 + 4
f(n) = 16.(2.f(n-5) + 4) + 32 + 16 + 8 + 4 = 32.f(n-5) + 64 + 32 + 16 + 8 + 4
...
f(n) = 2k.f(n-k) + σ𝑖=2
𝑘+12𝑖
Caso-base é alcançado quando k = n-1:
f(n) = 2n-1.f(1) + σ𝑖=2
𝑛 2𝑖
f(n) = 2n-1 . 3 + 2n+1 – 4 = (2+1) 2n-1 + 2n+1 – 2
= 2n+ 2n-1 + 2n+1 – 2 = 2n+1+ 2n+2n-1 – 4 = O(2n)
𝑓 𝑛 = 3 , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 2. 𝑓 𝑛 − 1 + 4, 𝑠𝑒 𝑛 > 1
෍
𝑖=0
𝑛
𝑎𝑖 =
𝑎𝑛+1 − 1
𝑎 − 1
(a ≠ 1)
Projeto e Análise de Algoritmos44
Recursividade
➢ Torre de Hanoi (hanoi.cpp):
void hanoi(int discos, int origem, int destino, int aux) {
if (discos == 1) {
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
return;
}
hanoi(discos-1, origem, aux, destino);
printf(“Mover 1 disco de %d para %d\n”, origem, destino);
hanoi(discos-1, aux, destino, origem);
}
𝑓 𝑛 = 𝑂 1 , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 2. 𝑓 𝑛 − 1 + 𝑂(1), 𝑠𝑒 𝑛 > 1
Projeto e Análise de Algoritmos45
Recursividade
➢ Aplicando o método da iteração:
f(n) = 2.f(n-1)
f(n) = 2.(2.f(n-2)) = 4.f(n-2)
f(n) = 4.(2.f(n-3)) = 8.f(n-3)
f(n) = 8.(2.f(n-4)) = 16.f(n-4)
f(n) = 16.(2.f(n-5)) = 32.f(n-5)
...
f(n) = 2k.f(n-k)
Caso-base é alcançado quando k = n-1:
f(n) = 2n-1.O(1)
f(n) = 2n-1 = O(2n)
𝑓 𝑛 = 𝑂(1) , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 2. 𝑓 𝑛 − 1 + 2, 𝑠𝑒 𝑛 > 1
Projeto e Análise de Algoritmos46
Recursividade
➢ Fibonacci recursivo (fibonacci.cpp):
int fib(int n) {
if (n == 1)
return 0;
if (n == 2)
return 1;
return fib(n-1) + fib(n-2);
}
𝑓 𝑛 = 2 , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 3 , 𝑠𝑒 𝑛 = 2
𝑓 𝑛 = 𝑓 𝑛 − 1 + 𝑓 𝑛 − 2 + 6, 𝑠𝑒 𝑛 > 2
Projeto e Análise de Algoritmos47
Recursividade
➢ Aplicando o método da iteração:
f(n) = f(n-1) + f(n-2)
f(n) = f(n-2)+f(n-3) + f(n-3)+f(n-4)
= f(n-2) + 2.f(n-3) + f(n-4)
f(n) = f(n-3)+f(n-4) + 2.f(n-4)+2.f(n-5) + f(n-5)+f(n-6)
= f(n-3) + 3.f(n-4) + 3.f(n-5) + f(n-6)
f(n) = f(n-4)+f(n-5) + 3.f(n-5)+3.f(n-6) + 3.f(n-6)+3.f(n-7) + f(n-7)+f(n-8)
= f(n-4) + 4.f(n-5) + 6.f(n-6) + 4.f(n-7) + f(n-8)
f(n) = f(n-5)+f(n-6) + 4.f(n-6)+4.f(n-7) + 6.f(n-7)+6.f(n-8) + 4.f(n-8)+4.f(n-9) +
f(n-9)+f(n-10)
= f(n-5) + 5.f(n-6) + 10.f(n-7) + 10.f(n-8) + 5.f(n-9) + f(n-10)
𝑓 𝑛 = 𝑂 1 , 𝑠𝑒 𝑛 = 1
𝑓 𝑛 = 𝑂(1) , 𝑠𝑒 𝑛 = 2
𝑓 𝑛 = 𝑓 𝑛 − 1 + 𝑓 𝑛 − 2 + 𝑂(1), 𝑠𝑒 𝑛 > 2
Onde está a equação geral?
Projeto e Análise de Algoritmos48
Recursividade
➢ Aplicando o método da substituição (prova por indução):
➢ Assuma que o algoritmo é O(2n), ou seja:
𝑓 𝑛 ≤ 2𝑛
➢ Hipótese: 𝑓 𝑛 ≤ 2𝑛 é verdade para n=1, 2, 3,..., k.
➢ Provar que essa relação vale para k+1: 𝑓 𝑘 + 1 ≤ 2𝑘+1
Projeto e Análise de Algoritmos49
Recursividade
➢ Provar que essa relação vale para k+1: 𝑓 𝑘 + 1 ≤ 2𝑘+1
𝑓 𝑘 + 1 ≤ 𝑓 𝑘 + 𝑓(𝑘 − 1)
𝑓 𝑘 + 1 ≤ 2𝑘 + 2𝑘−1
𝑓 𝑘 + 1 ≤
2
2
2𝑘 +
22
22
2𝑘−1
𝑓 𝑘 + 1 ≤
2𝑘+1
2
+
2𝑘+1
4
𝑓 𝑘 + 1 ≤
1
2
2𝑘+1 +
1
4
2𝑘+1
𝑓 𝑘 + 1 ≤ 2𝑘+1
1
2
+
1
4
𝑓 𝑘 + 1 ≤
3
4
2𝑘+1 , 𝑐𝑜𝑚𝑜
3
4
< 1 𝑒𝑛𝑡ã𝑜 𝑓 𝑘 + 1 ≤ 2𝑘+1
Assim, o algoritmo recursivo é O(2n).
Projeto e Análise de Algoritmos50
Recursividade
➢ Para ser exato, já foi provado que a complexidade do Fibonacci
recursivo é:
𝑓 𝑛 = 𝑂
1 + 5
2
𝑛
= 𝑂 1,618033…𝑛 𝑛՜∞
➢ Ou seja, a complexidade desse algoritmo é realmente exponencial!