Complexidade do tempo do programa

Question

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

 int main()

  {

    clock_t start;
    double d;
    long int n,i,j;
    scanf("%ld",&n);
    n=100000;
    j=2;
    start=clock();
    printf("\n%ld",j);

       for(j=3;j<=n;j+=2)
       {
          for(i=3;i*i<=j;i+=2)

          if(j%i==0)
            break;

           if(i*i>j)
          printf("\n%ld",j);

        }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;
    printf("\n%f",d);

}

Recebi o tempo de execução de 0,015 s quando n = 100000 para o programa acima. Também implementei a peneira do algoritmo Eratostótenes em C e tenho o tempo de execução de 0,046 para n = 100000.

Como é o meu algoritmo acima mais rápido que o algoritmo de Sieve que implementei.

Qual é a complexidade do tempo do meu programa acima ??

Implementação da minha peneira

 #define LISTSIZE 100000    //Number of integers to sieve<br>
 #include <stdio.h>
 #include <math.h>
 #include <time.h>

int main()
{   


    clock_t start;
    double d;
    long int list[LISTSIZE],i,j;
    int listMax = (int)sqrt(LISTSIZE), primeEstimate = (int)(LISTSIZE/log(LISTSIZE));

    for(int i=0; i < LISTSIZE; i++)
        list[i] = i+2;
    start=clock();

    for(i=0; i < listMax; i++)
    {
        //If the entry has been set to 0 ('removed'), skip it
        if(list[i] > 0)
        {
            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                if((list[j] % list[i]) == 0)
                    list[j] = 0;
            }
        }
    }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;

    //Output the primes
    int primesFound = 0;
    for(int i=0; i < LISTSIZE; i++)
    {
        if(list[i] > 0)
        {
            primesFound++;

            printf("%ld\n", list[i]);
        }
    }
    printf("\n%f",d);
    return 0;
}

Answer 1

Há várias coisas que podem influenciar seu resultado. Para ter certeza, precisaríamos ver o código para sua implementação de peneira. Além disso, qual é a resolução do clock função no seu computador? Se a implementação não permitir um alto grau de precisão no nível de milissegundos, seus resultados poderão estar dentro da margem de erro para sua medição.

Eu suspeito que o problema está aqui:

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                    if((list[j] % list[i]) == 0)
                            list[j] = 0;
            }

Esta é uma maneira ruim de remover todos os múltiplos do número principal. Por que não usar o operador de multiplicação embutido para remover os múltiplos? Esta versão deve ser muito mais rápida:

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = list[i]; j < LISTSIZE; j+=list[i])
            {
              list[j] = 0;
            }

Answer 2

Qual é a complexidade do tempo do meu programa acima ??

Para medir empiricamente a complexidade do tempo do seu programa, você precisa de mais de um ponto de dados. Execute seu programa para vários valores de n e faça um gráfico de n vs. tempo. Você pode fazer isso usando uma planilha, GNUplot ou papel gráfico e lápis. Você também pode usar software e/ou matemática antiga simples para encontrar uma curva polinomial que se encaixe nos seus dados.

Não empréstimo: Muito foi escrito (e lecionado em aulas de ciência da computação) sobre a análise da complexidade computacional. O artigo da Wikipedia sobre Teoria da complexidade computacional Pode fornecer alguns pontos de partida para leitura adicional.

Answer 3

Sua implementação de peneira está incorreta; Essa é a razão pela qual é tão lento:

• Você não deve fazer disso uma variedade de números, mas uma variedade de bandeiras (você ainda pode usar int como tipo de dados, mas char também faria)
• Você não deve estar usando turnos de índice para a matriz, mas a lista [i] deve determinar se eu é um primo ou não (e não se I+2 é um primo)
• você deve começar a eliminação com i = 2
• Com essas modificações, você deve seguir o conselho da 1800 Information e cancelar todos os múltiplos de i com um loop que vai em etapas de i, não etapas de 1

Answer 4

Apenas para sua complexidade de tempo:

Você tem um loop externo de ~ listmax iterações e um loop interno do máximo. Listize iterações. Isso significa que sua complexidade é

O (Sqrt (n)*n)

onde n = lista. Na verdade, é um pouco menor, pois o loop interno reduz sua contagem de tempo e é executada apenas para cada número desconhecido. Mas isso é difícil de calcular. Como a notação O oferece um limite superior, O (Sqrt (N)*N) deve estar ok.

Answer 5

O comportamento é difícil de prever, mas você deve levar em consideração que o acesso à memória não é barato ... provavelmente é mais rápido calculá -lo novamente para pequenos primos.

Answer 6

Esses tempos de corrida são pequenos demais para serem significativos. A resolução do relógio do sistema não é precisa para esse tipo de nível.

O que você deve fazer para obter informações de tempo preciso é executar seu algoritmo em um loop. Repita algumas milhares de vezes para obter o tempo de execução para pelo menos um segundo, então você pode dividir o tempo pelo número de loops.