Proponha um algoritmo que calcule o MDC de dois números dados e encontre o tempo de execução desse algoritmo. Dica: procure entender a idéia do algoritmo de Euclides e tente estimar seu tempo observando o argumento que modifica a cada chamada recursiva. Você pode propor um limite inferior e um superior para sua função. Considere exemplos com os números 20,15 e depois com os números 92,72 .

Passo 1

O enunciado pede para propor um algoritmo que calcule o máximo divisor comum (MDC) de dois números inteiros dados e estimar seu tempo de execução. O conteúdo é o algoritmo de Euclides e a análise de complexidade recursiva. Para resolver precisamos: (a) apresentar o procedimento recursivo de Euclides; (b) modelar o tempo de execução por uma recorrência; (c) estimar quantas chamadas recursivas ocorrem no pior e no melhor caso; (d) testar nos pares (20,15) e (92,72).

Passo 2

O algoritmo de Euclides para \text{MDC}(a,b) é:
  • Se b = 0, retorna a.
  • Caso contrário, retorna \text{MDC}\bigl(b,\;a \bmod b\bigr).
Em pseudo-texto:
“Dada a entrada (a,b), se b for zero então devolve a; senão faz uma chamada recursiva com os parâmetros b e a \bmod b.”

Passo 3

Justificativa da correção: a propriedade fundamental é
\gcd(a,b) \;=\;\gcd\bigl(b,\,a\bmod b\bigr)
e quando b=0 sobra \gcd(a,0)=a. Assim, ao reduzir recursivamente o segundo argumento até chegar a zero, o primeiro argumento final é o MDC.

Passo 4

Para analisar o tempo, seja T(a,b) o número de operações (divisão/resto) até a parada. Para b>0 temos
T(a,b)=T\bigl(b,\;a\bmod b\bigr)+C,
onde C é uma constante que conta a operação de resto e o teste. O número de chamadas recursivas é igual ao número de vezes que aplicamos (x,y)\mapsto(y,\,x\bmod y) até chegar em (d,0).

Passo 5

No pior caso, quando (a,b) são pares consecutivos de Fibonacci, cada chamada produz um par de índices decrescentes de Fibonacci, e o número de chamadas é \Theta(\log b). Logo, existe constante k tal que
T(a,b)\le k\,\log(\min\{a,b\}) + C'.
No melhor caso, basta uma chamada (por exemplo se b divide a), então
T(a,b)=\Omega(1).
Em notação assintótica para n=\min\{a,b\}:
\Omega(1)\;\le\;T(n)\;\le\;O(\log n).

Passo 6

Exemplo \text{MDC}(20,15):
( 20,15) \to resto 20\bmod15=5 \to ( 15,5) \to resto 15\bmod5=0 \to ( 5,0) e retorna 5.
Foram 2 operações de resto e 2 chamadas recursivas antes de chegar em b=0.

Passo 7

Exemplo \text{MDC}(92,72):
( 92,72) \to resto 92\bmod72=20 \to ( 72,20) \to resto 72\bmod20=12 \to ( 20,12) \to resto 20\bmod12=8 \to ( 12,8) \to resto 12\bmod8=4 \to ( 8,4) \to resto 8\bmod4=0 \to ( 4,0) e retorna 4.
Foram 5 operações de resto e 5 chamadas recursivas até b=0.

Resposta

O algoritmo de Euclides recursivo calcula \gcd(a,b) em tempo T(a,b) que satisfaz
\Omega(1)\;\le\;T(a,b)\;\le\;O\bigl(\log(\min\{a,b\})\bigr).
Nos exemplos, \text{MDC}(20,15)=5 em 2 iterações, e \text{MDC}(92,72)=4 em 5 iterações.

Exercícios relacionados