Jump to content
Metaluim

Complexidade do Trial Division

Recommended Posts

Metaluim

Boa noite,

Para uma cadeira tenho um trabalho que é implementar um algoritmo de factorização de inteiros e classifica-lo na sua ordem de complexidade e complexidade temporal. A professora deu-nos também um conjunto de inputs para testar. O algoritmo que implementei foi o trial division, assim por alto:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char **argv)
{
    int i, cnt = 0;
    long n = atol(argv[1]);

    time_t t1, t2;

    time(&t1);
    for (i = 2; i < n / i; i++, cnt++)
    {
        while (!(n % i))
        {
            n /= i;
            cnt++;
        }
    }
    time(&t2);

    printf("n_ops: %d\n", cnt);
    printf("time taken: %f\n", (double) (t2-t1));

    exit(0);
}

A ordem de complexidade calculei como sendo O(n) e o tamanho do input log2 (n), que é o número de bits. Agora a complexidade temporal é outra história. Andei aqui às voltas mas nenhuma das funções acho que está próxima dos resultados. Sei que tem que ser exponencial, mas como é que chego a essa expressão final? Acho que me está aqui a falhar qualquer coisa, mas deveria de ser O(log2 (n)) sendo o log2 (n) o tamanho do input e a ordem O(n) mas no entanto, os valores são totalmente diferentes. Como é que consigo comprovar isto? É que tenho que explicar por palavras como é que cheguei a este resultado e porque é que está certo e sinceramente não sei como comprovar se está ou não certa a complexidade temporal.

Se me conseguissem ajudar nisto de uma forma pragmática ficava-vos grato. :)

Share this post


Link to post
Share on other sites
Tharis

Não percebi o teu código para a trial division. Qual o objectivo de:

        while (!n % i)
        {
            n /= i;
            cnt++;
        }

ou

for (i = 2; i < n / i; i++, cnt++)

Repara que o ciclo while nunca é executado.

(!n % i)

é diferente de

(!(n%i))

. http://codepad.org/KVJFGWeW

Dá uma olhadela na página da Wiki sobre Trial Division. http://en.wikipedia.org/wiki/Trial_division

Cumps :)

Tharis

Share this post


Link to post
Share on other sites
Warrior

O(sqrt(n)), como aliás eu acho que são todos os algoritmos de factorização. (tirando talvez alguns mais complicados que desconheça)

No worst case em que n é um quadrado perfeito terás que testar até à sua raiz quadrada.

Share this post


Link to post
Share on other sites
Metaluim

O meu problema é mesmo esse, porque é que é raíz quadrada?

EDIT: o while fui eu que passei mal :S

Share this post


Link to post
Share on other sites
KTachyon

Porque até à raíz quadrada consegues sempre encontrar um factor.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
mogers

Acho que se mudares

for (i = 2; i <= n / i; i++, cnt++)

para o seu equivalente que é normalmente usado

for (i = 2; i * i <= n ; i++, cnt++)

fica muito mais facil de ver que de facto fazes sqrt(N) iterações

PS: era <= e não <


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Metaluim

Obrigado pelas respostas, já entendi o porquê da raíz quadrada. Só mais um pequeno pormenor, neste caso então, o tamanho do input será o próprio número e não o seu número de bits certo?

Share this post


Link to post
Share on other sites
Warrior

Sim, N = número lido.

Se quiseres considerar que N = número de bits, então sim, terás uma complexidade exponencial.

Mas a minha opinião é que não faz muito sentido analisar a complexidade com base no número de bits do input, porque mudando a representação do input mudaria a complexidade da tua solução.

Share this post


Link to post
Share on other sites
mogers

só uma coisa, o teu cnt não contabiliza a comparação no ciclo ( i*i <= n), nem o  "i=2"  (se quiseres ir a esse detalhe)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Metaluim

Sim, N = número lido.

Se quiseres considerar que N = número de bits, então sim, terás uma complexidade exponencial.

Mas a minha opinião é que não faz muito sentido analisar a complexidade com base no número de bits do input, porque mudando a representação do input mudaria a complexidade da tua solução.

Pois começo a ver que não, o problema foi que a senhora doutora professora explicou isto extremamente mal e eu fiquei a impressão errada do problema. Só depois de andar a ler melhor é que cheguei à conclusão que realmente não faz muito sentido usar os bits.

só uma coisa, o teu cnt não contabiliza a comparação no ciclo ( i*i <= n), nem o  "i=2"  (se quiseres ir a esse detalhe)

Se fizer isso, os valores já ficam um (bom) bocado diferentes de sqrt(n), será que deva analisar essas operações? :S

Share this post


Link to post
Share on other sites
Warrior

Esta notação pretende indicar exactamente o número de operações, mas sim a velocidade de crescimento, portanto é praticamente indiferente.

Share this post


Link to post
Share on other sites
Metaluim

Esta notação pretende indicar exactamente o número de operações, mas sim a velocidade de crescimento, portanto é praticamente indiferente.

Exacto, pelo que percebi o que importa mesmo é analisar a curva e não propriamente os resultados da função da complexidade.

Já consegui acabar o trabalho, obrigado a todos pela ajuda ;)

Share this post


Link to post
Share on other sites
mogers

Pois, não esquecer o factor constante em qualquer pedaço de código (embora neste algoritmo nem seja muito visivel), nunca vais ter algo exactamente ops=função(N)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Rui Carlos

Mas a minha opinião é que não faz muito sentido analisar a complexidade com base no número de bits do input, porque mudando a representação do input mudaria a complexidade da tua solução.

Isso só acontece porque ao medir a complexidade baseado em código são feitas certas simplificações que podem deixar de fazer sentido quando mudas a representação (se passares para representação "unária", deixas de poder assumir que as operação aritméticas são realizadas em tempo constante).

Diria que se implementares o algoritmo com uma Máquina de Turing, qualquer que seja a representação, obténs a mesma complexidade. Numa MT se quiseres considerar o tamanho do input como o próprio N, basta usar representação "unária". Mas ao fazeres isto, vais complicar as operações aritméticas, que passarão a ter complexidade maior. Da mesma forma, se usares representação decimal, as operações aritméticas ficam mais simples, mas ao mesmo tempo o tamanho do input também fica mais pequeno (log10 em vez de log2).

Ou seja, a complexidade deverá ser sempre a mesma independentemente da representação.

Resumindo, o tamanho do input a considerar deve ser log2(N) e não N.

De referir ainda que caso contrário a complexidade da factorização não seria um valor muito realista. A factorização de números grandes é intratável para certos inputs, o que não devia acontecer com um algoritmo de complexidade O(sqrt(n)).

Share this post


Link to post
Share on other sites
Warrior

Discordo completamente do que acabaste de dizer.

Se considerares N = número de bits e K o valor representado, o próprio acto de fazer um ciclo for para somar todos os valores de 1 até K pode ser representado por O(2^N) ou por O(K). Tudo depende de qual a variável a considerar, porque o número de bits e o valor representado são objectivamente variáveis diferentes.

O problema é que ao indicar a complexidade nunca detalhamos convenientemente o que representam as variáveis que usamos.

Em relação à factorização de números grandes, é verdade que isso é usado em algoritmos de encriptação, mas estamos a falar de números tão grandes que até a sua raiz quadrada é grande.

Por exemplo, RSA-768 utiliza 768 bits e portanto estamos a falar de números com 232 dígitos. Se considerares que a raíz quadrada te divide o número de dígitos por 2 (simplificação grosseira, mas bastante aproximada) continuas a ter um número gigantesco para iterar.

Além disso, os números a factorizar são escolhidos a partir do produto de 2 primos também eles grandes, para evitar grandes cortes na pesquisa.

Já agora, acho que frequentemente se sobreestima inconscientemente o poder de raízes quadradas na complexidade. Apesar de todos sabermos a diferença, tratamos por vezes os termos como se logaritmos fossem.

Share this post


Link to post
Share on other sites
Rui Carlos

Se usas binário, o tamanho do input é N=log2(K). Para teres um input de tamanho K, precisavas de usar a representação unária. Mas quando mudas a forma como armazenas os números em memória, o número de passos necessários para executar uma operação também muda.

No entanto isto é difícil de ver num computador, pois internamente ele usa sempre binário. Adicionalmente, quando trabalhamos com números pequenos, ainda se simplifica a complexidade de operações aritméticas (que não são O(1)). Mas quando usamos uma MT, estes pormenores ficam explícitos. E aí nunca vi nenhum algoritmo mudar de complexidade quando mudas a representação da informação (mas é possível que algumas operações admitam algoritmos mais simples/de menor complexidade, em determinadas representações).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.