c - 我是否只是证明了埃拉托色尼筛法的效率低于试验划分？

Question

我试图比较两种算法的运行时速度:一个用于打印素数(10,000 个数字)的强力 C 程序和一个 C 程序埃拉托色尼筛法(也是 10,000 个素数)。

我测得的筛选算法运行时间是:0.744 秒

我测得的蛮力算法运行时间是:0.262 秒

但是，有人告诉我埃拉托色尼筛法算法比蛮力法更有效，所以我认为它会运行更快。所以要么我错了，要么我的程序有缺陷(我对此表示怀疑)。

因此，我的问题是:由于我得到的结果与我的预期相反，这是否证明埃拉托色尼筛法在速度方面确实是效率较低的算法，相比之下去审判部？

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

Answer 1

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

---

仅在一种输入大小下测量两种实现的速度是不够的。通常需要几个数据点来评估运行时间 empirical orders of growth我们的代码(因为代码可以在不同的输入大小下运行)。它是基于输入大小比率的运行时间比率的对数。

所以即使在一些输入code_1运行速度比 code_2 快 10 倍，但它的运行时间随着输入大小的每次加倍而加倍，而对于code_2它只会增长 1.1x，很快 code_2将变得比code_1快得多.

所以算法效率的真正衡量标准是它的 run time complexity (及其空间的复杂性，即内存要求)。当我们根据经验对其进行测量时，我们仅针对手头的特定代码(在特定的输入大小范围内)进行测量，而不是针对算法本身，即它的理想实现。

特别地，试分的理论复杂度为O(n^1.5 / (log n)^0.5) , 在 n 个素数中产生，通常被视为 ~ n^1.40..1.45增长的经验顺序(但对于较小的输入大小，最初可以是 ~n^1.3)。对于 Eratosthenes 的筛子，它是 O(n log n log (log n)) ，通常显示为 ~ n^1.1..1.2 .但是，在 ~n^2.0 运行的试验划分和埃拉托色尼筛法肯定存在次优实现。更糟的是。

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

预测 具有已知的确定性是 scientific method是关于。

---

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