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
e
.
Passo 2
O algoritmo de Euclides para
é:
- Se
, retorna . - Caso contrário, retorna
.
Em pseudo-texto:
“Dada a entrada , se
for zero então devolve
; senão faz uma chamada recursiva com os parâmetros
e
.”
“Dada a entrada
Passo 3
Justificativa da correção: a propriedade fundamental é
e quando
sobra
. Assim, ao reduzir recursivamente o segundo argumento até chegar a zero, o primeiro argumento final é o MDC.
Passo 4
Para analisar o tempo, seja
o número de operações (divisão/resto) até a parada. Para
temos
onde
é 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
até chegar em
.
Passo 5
No pior caso, quando
são pares consecutivos de Fibonacci, cada chamada produz um par de índices decrescentes de Fibonacci, e o número de chamadas é
. Logo, existe constante
tal que
No melhor caso, basta uma chamada (por exemplo se
divide
), então
Em notação assintótica para
:
Passo 6
Exemplo
:
( )
resto
(
)
resto
(
) e retorna
.
Foram operações de resto e
chamadas recursivas antes de chegar em
.
(
Foram
Passo 7
Exemplo
:
( )
resto
(
)
resto
(
)
resto
(
)
resto
(
)
resto
(
) e retorna
.
Foram operações de resto e
chamadas recursivas até
.
(
Foram
Resposta
O algoritmo de Euclides recursivo calcula
em tempo
que satisfaz
Nos exemplos,
em
iterações, e
em
iterações.