我刚才证明了埃拉托斯特尼的筛分效率低于试验部门吗？

Question

我试图比较两种算法的运行时速度：一个强制C程序打印质数（10000个数字），和一个Eratosthennes C程序筛选（10000个质数）。

我为sieve算法测得的运行时间是:0.744秒

我测量的暴力算法的运行时间为：0.262 秒

然而，有人告诉我，厄拉多塞算法的筛子比蛮力方法更有效，所以我认为它会运行得更快。所以要么是我错了，要么是我的程序有缺陷(对此我表示怀疑)。

因此，我的问题是：由于我得到了与我预期相反的结果，这是否证明了就速度而言，埃拉托斯特尼筛真的是比试算法效率更低的算法？

我不确定它是否有任何相关性，但我正在使用Dev C编译器和Windows 7。

Answer 1

较长的运行时间是否意味着算法效率较低？

不需要。衡量计划效率的不仅是时间，而且是资源。空间是考虑效率时要记住的另一个因素。

来自维基:-

为了最大化效率，我们希望最小化资源使用。然而，各种资源(例如，时间、空间)不能被直接比较，因此两种算法中哪一种被认为更有效通常取决于哪种效率度量被认为是最重要的，例如，是对高速的要求，还是对最小存储器使用的要求，还是对一些其他度量的要求？

Answer 2

不，运行时间并不是衡量效率的标准，因为不同平台的运行时间不同——“我的算法在10秒钟内运行”几乎没有给出关于算法本身的信息。除此之外，您还需要列出整个环境规范和同时运行的其他进程，这将是一个巨大的混乱。因此，顺序符号的发展（Big Oh、Little Oh、Omega等）。

效率通常分为两个小节：

1. 时间效率
2. 空间效率

...其中一种算法可能具有极高的时间效率，但在空间方面却非常低效。反之亦然。算法在扩展给定输入 n 需要执行的指令量时，根据其渐近行为进行分析。这是一个由博士计算机科学家精心研究的领域的一个非常高级的解释 - 我建议你在这里阅读更多关于它的信息，以获得你能找到的最好的低层次解释。

注意，我附上了大Oh符号的链接-姐妹符号都可以在维基百科页面上找到，这通常是一个很好的起点。它也将进入空间和时间效率的差异。

小应用的时间效率用大哦:

考虑一下Racket中的以下递归函数（如果我知道的话，它会在Python中——我能做的最好的伪代码）：

(define (fn_a input_a)
  (cond
    [(empty? input_a) empty]
    [(empty? (rest input_a)) input_a]
    [(> (first input_a) (fn_a (rest input_a))) (cons (first input_a) empty)]
    [else (fn_a (rest input_a))]))

...我们看到：空的？，Rest，

同样重要的是要注意，根据Big Oh的正式定义，声明fn_a是O（3^n）也是正确的（但是没用）。许多算法在分析时使用Big Oh表示，但是使用Big Theta来收紧界限会更合适，本质上意味着：相对于给定算法的最低、最准确的顺序。

小心，阅读正式定义！

Answer 3

太长别读：仅在一个输入大小下比较代码变体的速度是没有意义的；比较经验增长顺序真正反映了代码的算法性质，并且对于相同的输入大小测试范围，在不同的测试平台上是一致的。比较绝对速度值仅对表现出相同渐近或至少局部增长行为的代码变体有意义。

仅仅以一个输入大小来衡量两个实现的速度是不够的。通常需要几个数据点来评估我们代码增长的运行时经验顺序（因为代码可以在不同的输入大小下运行）。它是运行时间比率的对数，以输入大小的比率为基础。

因此，即使在某些输入code_1运行速度比code_2快10倍，但其运行时间随着输入大小的每增加一倍而增加一倍，而对于code_2它仅增长1.1倍，很快code_2将变得比code_1快得多。

因此，衡量算法效率的真正标准是其运行时复杂性（以及其空间复杂性，即内存需求）。当我们根据经验测量它时，我们只测量手头的特定代码（在特定的输入大小范围内），而不是算法本身，即它的理想实现。

特别是，在生成的n个素数中，试验划分的理论复杂度为O（n^1.5/（logn）^0.5），通常被视为经验增长顺序（但对于较小的输入大小，最初可以是~n^1.3。对于埃拉托斯特尼的筛分，它是O（n log n log（log n）），通常被视为~n^1.1…1.2。但是，在~n^2.0或更糟的情况下，肯定存在试验分区和埃拉托斯尼筛的次优实现。

所以不，这证明不了什么。一个数据点是没有意义的，至少需要三个数据点才能获得“大局”，即能够确定地预测更大输入大小所需的运行时间/空间。

已知确定性的预测是科学方法的全部内容。

顺便说一下，你的运行时间很长。对10，000个素数的计算应该几乎是瞬间的，远小于在一个快速机器上运行的C程序的1/100秒。也许你也在测量打印时间。不要。:)