Por que o algoritmo de divisão por tentativa é exponencial?

Por
| 

O algoritmo de divisão por tentativa, para quem não sabe, é um algoritmo de fatoração de números inteiros.

Recentemente, eu recebi um comentário de um leitor questionando o porquê do algoritmo de divisão por tentativa ter complexidade exponencial, uma vez que no artigo onde eu apresento o mesmo não há uma justificativa. A ideia desta postagem é sanar essa dúvida.

Complexidade do algoritmo de divisão por tentativa

Vamos lá! O laço principal do algoritmo percorre todos os números ímpares até $\sqrt{n}$.

01. trialDivision(n)
02. |   enquanto(n % 2 = 0)
03. |   |   imprima 2
04. |   |   n ← n / 2
05. |   fim_enquanto
06. |   d ← 3
07. |   enquanto(d2 ≤ n)
08. |   |   se(n % d = 0)
09. |   |   |   imprima d
10. |   |   |   n ← n / d
11. |   |   senão
12. |   |   |   d ← d + 2
13. |   |   fim_se
14. |   fim_enquanto
15. |   se(n > 1)
16. |   |   imprima n
17. |   fim_se
18. fim_trialDivision

Numa primeira aproximação, poderíamos dizer que a complexidade no tempo seria $O(\sqrt{n})$. Mas isso não é exponencial!

O "pulo do gato" é que estamos ignorando algo fundamental na análise da complexidade: as operações aritméticas. Usualmente, ao analisar um algoritmo, consideramos que essas operações têm complexidade constante. Isso acontece porque na maioria das vezes os números são tipos primitivos com no máximo 64 bits.

Contudo, quando lidamos com números de precisão arbitrária, não podemos ignorar o tamanho dos números, pois o tempo de execução das operações aritméticas irá aumentar em função da quantidade de bits que os operandos possuem.

Para sanar este problema, é comum expressar o número em função da quantidade de bits que ele possui. Se $b$ é o número de bits, então $n$ não ultrapassará $2^b$.

Portanto, substituindo $n$ por $2^b$, teremos

$$T(n)=O(\sqrt{2^b})=O(2^{b/2})$$

Isso conclui a demonstração.


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

»