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.
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.
Nenhum comentário:
Postar um comentário