程序的时间复杂度

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

有很多因素可能会影响您的结果。可以肯定的是，我们需要查看您的筛子实现的代码。另外，您计算机上时钟功能的分辨率是多少？如果实施不允许达到毫秒级的高精度，那么您的结果可能会在测量误差范围内。

我怀疑问题出在这里：

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

我上面的程序的时间复杂度是多少？

为了凭经验测量程序的时间复杂度，您需要多个数据点。针对多个 N 值运行程序，然后绘制 N 与时间的关系图。您可以使用电子表格、GNUplot 或方格纸和铅笔来完成此操作。您还可以使用软件和/或简单的旧数学来找到适合您的数据的多项式曲线。

非经验性：关于分析计算复杂性，已经写了很多文章（并在计算机科学课程中讲授）。关于计算复杂性理论的维基百科文章可能会为进一步阅读提供一些起点。

Answer 3

您的筛子实施不正确；这就是为什么它这么慢的原因：

• 你不应该把它变成一个数字数组，而是一个标志数组（你仍然可以使用 int 作为数据类型，但 char 也可以）
• 你不应该使用索引数组的移位，但 list[i] 应该确定 i 是否是素数（而不是 i+2 是否是素数），
• 您应该通过这些修改从 i=2 开始消除
• ，您应该遵循 1800 INFORMATION 的建议，并使用以 i 步长而不是 1 步长的循环取消 i 的所有倍数

Answer 4

只是为了您的时间复杂度：

您有一个 ~LISTMAX 迭代的外循环和一个 max 的内循环。 LISTSIZE 迭代。这意味着你的复杂性是

O(sqrt(n)*n)

其中 n = 列表大小。它实际上要低一些，因为内部循环每次都会减少计数，并且仅针对每个未知数运行。但这很难计算。由于 O 表示法提供了上限，因此 O(sqrt(n)*n) 应该没问题。

Answer 5

这种行为很难预测，但您应该考虑到访问内存并不便宜......对于小素数再次计算它可能会更快。

Answer 6

这些运行时间太短，没有意义。系统时钟分辨率不准确到这种水平。

为了获得准确的计时信息，您应该做的是循环运行您的算法。重复数千次以使运行时间至少达到一秒，然后您可以将时间除以循环次数。