プログラムの時間計算量

StackOverflow https://stackoverflow.com/questions/1353252

質問 

 #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;
}
役に立ちましたか？

解決

あなたの結果に影響を与える可能性がある事柄がいくつかあります。確かに、我々はあなたのふるいの実装のためのコードを参照する必要があります。また、コンピュータ上の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;
            }

他のヒント

  

私の上記のプログラム??

の時間複雑さは何ですか

経験的に、あなたのプログラムの時間計算量を測定するには、複数のデータポイントを必要としています。時間対Nのグラフを作成し、その後、Nの複数の値のために、あなたのプログラムを実行します。スプレッドシートはgnuplot、またはグラフ紙と鉛筆を使ってこれを行うことができます。また、あなたのデータをフィットする多項式曲線を見つけるために、ソフトウェアおよび/または、昔ながらの数学を使用することができます。

非経験的に：あまり書かれた（とコンピュータサイエンスの授業で講義）計算の複雑さを分析することについてはされています。 計算複雑性理論上のWikipediaの記事はには、さらに読書のためのいくつかの出発点を提供することがあります。

sieve の実装が間違っています。それがとても遅い理由です:

  • 数値の配列ではなく、フラグの配列にする必要があります (データ型として int を使用することもできますが、char も同様に使用できます)。
  • 配列のインデックスシフトを使用すべきではありませんが、list[i] は i が素数かどうか (i+2 が素数かどうかではなく) を決定する必要があります。
  • i=2 から消去を開始する必要があります
  • これらの変更を加えた場合は、1800 INFORMATION のアドバイスに従って、1 のステップではなく i のステップで進むループで i の倍数をすべてキャンセルする必要があります。

ちょうどあなたの時間の複雑さのために：

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

  

O（SQRT（N）* N）

ここで、n = LISTSIZE。内側のループは、それがeacht時間をカウントだ低減し、各未知数のためにのみ実行されるため、実際に少し低くなっています。しかし、それは計算するのは困難です。 O-表記が上限を提供していますので、O（SQRT（N）* n）は[OK]をする必要があります。

それだけで小さな素数のために再びそれを計算するために、おそらく高速です...行動を予測することは困難ですが、メモリへのアクセスは安くはないことを考慮に入れる必要があります。

これらの実行時間は、意味のあるものには小さすぎます。システム・クロックの分解能は、レベルのようなものに正確ではない。

あなたが正確なタイミング情報を取得するために何をすべきかは、ループの中で、あなたのアルゴリズムを実行しています。その後、あなたはループの数によって時間を分割することができ、少なくとも第二に実行時間を得るためにそれを数千回繰り返します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top