Dados dois inteiros e de bits cada, podemos aplicar o algoritmo de Euclides para obter o . Ao estudar este algoritmo, Dylan foi desafiado a obter um algoritmo por divisão e conquista para obter . Ele teve a seguinte inspiração divina:
Assim, T(2 n)=2 c sumi=1^n i. O que implica em O(n^2).
(d) Dylan obteve algum ganho de complexidade em relação ao algoritmo de Euclides? (Dica: lembre da complexidade da multiplicação de dois inteiros de n bits cada, assim como da dica do item 9c).
Resposta:
O algoritmo de Euclides possui complexidade O(n^3). Assim, o algoritmo do item anterior é mais eficiente.
Passo 1
O enunciado pede para validar e implementar uma versão “dividir e conquistar” do cálculo de gcd(a,b) usando apenas subtrações e divisões por 2, e depois analisar a recorrência e comparar com o método clássico de Euclides. Vamos precisar usar propriedades básicas de gcd, especialmente: extração de fator 2 e o fato de gcd(a,b)=gcd(a-b,b).
Passo 2
Prova de corretude:
– Se a e b são pares, escrevemos a=2a' e b=2b'. Então qualquer divisor comum de a,b também divide 2a',2b' e vice-versa, logo:
gcd(a,b)=2;gcd(a',b')
– Se a é ímpar e b=2b' é par, como 2 não divide a, podemos “tirar” o 2 de b sem afetar o gcd:
gcd(a,b)=gcd(a,2b')=gcd(a,b')
– Se a e b são ímpares, então a-b é par e valem ainda as propriedades:
gcd(a,b)=gcd(a-b,b),
e, escrevendo a-b=2c, volta ao caso anterior:
gcd(a,b)=gcd(2c,b)=gcd(c,b)
Passo 3
Algoritmo recursivo em pseudocódigo (supondo entrada a,b>=0):
se a=0 retorne (b);
se b=0 retorne (a);
se a=b) retorne (a);
se a e b são pares então retorne 2timesgcd(a/2,b/2);
se a é ímpar e b é par então retorne gcd(a,b/2);
se a é par e b é ímpar então retorne gcd(a/2,b);
// agora a e b são ímpares
se a>b) retorne gcd((a-b)/2,b) senão retorne gcd(a,(b-a)/2).
Passo 4
Análise de complexidade: Cada chamada faz no máximo uma subtração (custo O(n) para números de n bits) e/ou divisões por 2 (shift de bits, O(1)). Em todo caso a cada recursão o tamanho em bits de algum operando cai em pelo menos 1, gerando a recorrência
T(n)=T(n-1)+O(n)
Somando de 1 até n dá T(n)=O(n^2).
Passo 5
Comparação com Euclides clássico: O método de Euclides usa divisões (custo M(n), a complexidade de multiplicação/divisão de inteiros de n bits) repetidas O(n) vezes, resultando em O(n,M(n)). Com multiplicação bruta M(n)=O(n^2), isso dá O(n^3), logo o algoritmo “shift-subtraction” de Dylan é O(n^2) e melhora sobre o Euclides tradicional.