プログラムの時間複雑度

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

} 

上記のプログラムでn = 100000のとき、実行時間は0.015秒です。 私はCでシラバス・オブ・エラトステネスアルゴリズムを実装し、n = 100000の実行時間0.046を得ました。

上記のアルゴリズムは、私が実装したSieveのアルゴリズムよりも高速です。

私の上記のプログラムの時間の複雑さは何ですか？

マイふるいの実装

#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

あなたの結果に影響を与える可能性がある事柄がいくつかあります。確かに、あなたのふるいの実装のコードを見る必要があります。また、お使いのコンピュータのclock機能の解像度は？実装でミリ秒レベルで高い精度が得られない場合、結果は測定の誤差範囲内に収まる可能性があります。

私はこの問題はここにある疑いがある：

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

これは素数の倍数のすべてを除去するための貧弱な方法です。組み込みの乗算演算子を使用して倍数を削除してみませんか？このバージョンははるかに速くなければなりません：

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

篩の実装が正しくありません。それはそれはとても遅い理由です：

• あなたはそれの数字の配列が、フラグの配列にするべきではありません（あなたはまだデータ型としてintを使用することができますが、charは同様だろう）
• 配列のインデックスシフトを使用するべきではありませんが、リスト[i]はiが素数であるかどうかを判断する必要があります（i + 2が素数でないかどうか）。
• i = 2
• これらの変更では、1800 INFORMATIONのアドバイスに従い、1のステップで行くループでiのすべての倍数をキャンセルする必要があります。1のステップではありません。

Answer 3

私の上記のプログラムの時間の複雑さは何ですか？

プログラムの時間複雑さを経験的に測定するには、複数のデータポイントが必要です。 Nの複数の値に対してプログラムを実行し、N対時間のグラフを作成します。スプレッドシート、GNUplot、またはグラフ紙と鉛筆を使用してこれを行うことができます。また、ソフトウェアや古くからある数学を使って、データに合った多項式曲線を見つけることもできます。

経験的ではありません：コンピュータの複雑さの分析については、多くのことが書かれています（コンピュータサイエンスのクラスで講義されています）。 computational complexity theoryに関するWikipediaの記事は、さらに読むためにいくつかの出発点を提供するかもしれない。ちょうどあなたの時間の複雑さのため

Answer 4

：

あなたは〜LISTMAX反復の外側のループとmaxの内側のループを持っています。反復をLISTSIZEします。これはあなたの複雑さは

O（SQRT（N）* n）の

のn = LISTSIZEであることを意味します。それは実際には内側のループがそれをカウントダウンし、それぞれの未知数に対してのみ実行されるので、少し下になります。しかしそれは計算が難しい。 O-表記法は上限を提供するので、O（sqrt（n）* n）は大丈夫です。

Answer 5

この動作は予測するのが難しいですが、メモリにアクセスすることは安価ではないことを考慮する必要があります。小さな素数については、再度計算するほうが速いでしょう。

Answer 6

これらの実行時間は意味がないほど小さすぎます。システムクロックの解像度は、その種のレベルでは正確ではありません。

正確なタイミング情報を得るために行うべきことは、アルゴリズムをループで実行することです。実行時間を少なくとも1秒にするには、数千回それを繰り返します。次に、ループの回数で時間を割ります。