la complexité du temps du programme

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);

}

Je suis le temps de fonctionnement de 0,015 sec lorsque n = 100000 pour le programme ci-dessus. J'ai aussi mis à exécution les Sieve de l'algorithme Eratosthène en C et a obtenu le temps de fonctionnement de 0,046 pour n = 100000.

Comment est mon algorithme ci-dessus plus rapide que l'algorithme de Sieve que j'ai mis en œuvre.

Quelle est la complexité du temps de mon programme ci-dessus ??

mise en œuvre de mon tamis

 #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

Il y a un certain nombre de choses qui pourraient influer sur le résultat. Certes, nous devons voir le code pour votre mise en œuvre du tamis. De plus, quelle est la résolution de la fonction clock sur votre ordinateur? Si la mise en œuvre ne permet pas un haut degré de précision au niveau de la milliseconde, alors vos résultats pourraient être dans la marge d'erreur pour votre mesure.

Je soupçonne que le problème se trouve ici:

            //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;
            }

Ceci est une mauvaise façon de supprimer tous les multiples du nombre premier. Pourquoi ne pas utiliser les fonctions intégrées dans l'opérateur de multiplication pour éliminer les multiples? Cette version devrait être beaucoup plus rapide:

            //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

  

Quelle est la complexité du temps de mon programme ci-dessus ??

Pour mesurer de façon empirique la complexité temporelle de votre programme, vous avez besoin de plus d'un point de données. Exécutez votre programme pour plusieurs valeurs de N, puis faire un graphique de N en fonction du temps. Vous pouvez le faire en utilisant une feuille de calcul, GNUplot ou du papier quadrillé et un crayon. Vous pouvez également utiliser le logiciel et / ou mathématiques pures et simples pour trouver une courbe polynomiale qui correspond à vos données.

non-empirique: on a beaucoup écrit (et donne des conférences dans les classes de sciences informatiques) sur l'analyse de la complexité. L'article de Wikipedia sur théorie de complexité pourrait fournir des points de départ pour aller plus loin.

Answer 3

Votre mise en œuvre du tamis est incorrect; c'est la raison pour laquelle il est si lent:

• vous ne devriez pas faire un tableau de nombres, mais un tableau de drapeaux (vous pouvez toujours utiliser int comme type de données, mais ombles feriez aussi bien)
• vous ne devriez pas utiliser les changements d'index pour le tableau, mais la liste [i] doit déterminer si i est un premier ou non (et pas si i + 2 est un premier)
• vous devriez commencer à éliminer avec i = 2
• avec ces modifications, vous devez suivre les conseils de 1800 INFORMATIONS, et annuler tous les multiples de i avec une boucle qui va dans les étapes de i, non pas de 1

Answer 4

Juste pour la complexité de votre temps:

Vous avez une boucle externe d'itérations ~ LISTMAX et une boucle interne de max. itérations ListSize. Cela signifie que votre complexité est

  

O (sqrt (n) * n)

où n = ListSize. Il est en fait un peu plus bas depuis la boucle interne réduit, il est temps compter chaque chiffre et est exécuté seulement pour chaque numéro inconnu. Mais ce qui est difficile à calculer. Depuis la notation O offre une limite supérieure, O (sqrt (n) * n) devrait être ok.

Answer 5

Le comportement est difficile à prévoir, mais vous devez tenir compte du fait que l'accès à la mémoire est pas cher ... il est probablement plus rapide de calculer tout nouveau pour les petits nombres premiers.

Answer 6

Les temps d'exécution sont trop petites pour être significative. La résolution de l'horloge système est pas exact de ce genre de niveau.

Ce que vous devez faire pour obtenir des informations précises de synchronisation est exécuté votre algorithme dans une boucle. Répétez quelques milliers de fois pour obtenir le temps de fonctionnement jusqu'à au moins une seconde, vous pouvez diviser le temps par le nombre de boucles.