logo标签列表

我刚刚证明了埃拉托斯特尼筛法比试除法效率更低吗？

calgorithmprimesperformancesieve-of-eratosthenes
5
我试图比较两个算法的运行速度：一个是暴力枚举素数（10,000个数字）的C程序，另一个是埃拉托色尼筛法（也是10,000个素数）的C程序。
我的筛法算法测量运行时间为：0.744秒。
我的暴力算法测量运行时间为：0.262秒。
然而，我被告知埃拉托色尼筛法比暴力方法更有效率，所以我认为它应该运行得更快。因此，要么我错了，要么我的程序有缺陷（我不太相信后者）。
因此，我的问题是：由于我得到了与预期相反的结果，这是否证明埃拉托色尼筛法在速度上确实是比试除法更低效的算法？
我不确定这是否相关，但我正在使用Dev C++编译器和Windows 7操作系统。
3
简短回答：不一定。算法的效率是渐进定义的（对于任意大的输入）。许多非常高效的算法从某种形式的缓存/预分配中获得它们的效率……这使得它们在处理小输入时比暴力算法更慢。然而，在您的情况下，我非常惊讶原始算法的表现优于埃拉托斯特尼筛法（基本上是一种“聪明”的暴力算法）。您对其实现百分之百确定吗？ - val
9
正确提问的方法应该是将您用来实现并测试这两个算法的代码发布。这样，我们就不必仅靠猜测来推测在某些情况下可能导致您看到的行为问题的原因，而是可以确切地告诉您代码哪里出了问题。此问题已被“暂停”，因为它不完整。您可以[编辑]它以包括您的代码和更详细的问题描述，以便重新开放它。 - Cody Gray
2
现在越来越常见的是，关闭的原因是**[自我审查]。对于这个问题，给出一个“几段”回答是完全合理的。以下是大纲：测量 经验性增长阶数 对于两种算法。一个点不够；三个点就足够了。** 就这些，这不是已经给出的答案之一。 - Will Ness
1
@CodyGray 我们仍然可以讨论一点大小的测量是否有意义，或者必须对更多的输入大小进行比较？即使我们对代码一无所知，也有一个答案。:) 我已经修改了问题，使其更具体。 - Will Ness
2
@starblue，显然我强烈不同意，这可以从我的回答中看出来。关于这个问题有一个有意义的讨论和有意义的答案。我希望我已经给出了。值得注意的是，无论代码如何，最好使用经验增长技术来评估其效率，并且仅在一个输入大小点上测量比较速度是没有意义的。 - Will Ness
显示剩余10条评论
6个回答
7
TL;DR：仅比较一个输入大小的代码变体速度是没有意义的；比较经验增长阶数真正反映了代码的算法性质，并且在相同的输入大小测试范围内，不同的测试平台将保持一致。比较绝对速度值仅对表现出相同渐进或至少局部增长行为的代码变体有意义。

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

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

所以，算法效率的真正衡量标准是它的运行时间复杂度（以及其空间复杂度，即内存需求）。当我们从经验上衡量它时，我们只测量特定代码（在特定输入大小范围内）的情况，而不是算法本身，即其理想实现。
特别地，试除法的理论复杂度为O(n^1.5 / (log n)^0.5)，在产生n个质数时，通常被视为~ n^1.40..1.45的经验增长阶数（但对于较小的输入大小，初始值可能为~n^1.3）。对于埃拉托色尼筛法，它是O(n log n log (log n))，通常被视为~ n^1.1..1.2。但是，试除法和埃拉托色尼筛法都有次优实现，运行速度为~n^2.0甚至更慢。
所以，这证明不了什么。一个数据点是毫无意义的，至少需要三个数据点才能得到“大局”即能够预测更大输入规模所需的运行时间/空间并具有一定的确定性。
使用已知确定性进行预测正是科学方法的全部内容。

顺便说一下，你的运行时间太长了。计算10,000个质数应该几乎是瞬间完成的，对于在快速计算机上运行的C程序来说，时间应该远远小于1/100秒。也许你还测量了打印时间。不要这样做。 :)

6
不，经过时间的运行并不是衡量效率的标准，因为它会因平台而异。简单地说“我的算法在10秒内运行”对算法本身几乎没有任何信息。此外，您需要列出整个环境规格和同时运行的其他进程，这将是一团糟。因此，产生了阶记（大O、小o、Omega等）的发展。
效率通常分为两个子部分：
1. 时间效率。 2. 空间效率。
在这里，一个算法可能非常高效，但空间效率非常低效。反之亦然。算法是基于它们在给定输入n时需要执行的指令数量的渐近行为进行分析的。这是一个非常高层次的解释，由计算机科学博士精心研究 - 我建议您在这里阅读有关最好的低级解释。
请注意，我附加了Big Oh符号的链接 - 所有姐妹符号都可以在那个维基百科页面上找到，这通常是一个很好的起点。它还将涉及空间和时间效率的差异。
使用Big Oh的时间效率的小应用程序：
考虑以下递归函数在Racket中（如果我知道Python，就会在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))]))

在我们看到的这个例子中，empty?、rest、> 和 first 的时间复杂度都是 O(1)。我们还注意到，在最坏情况下，第三个条件和第四个条件会在 input_a 的 rest 上调用 fn_a。因此，我们可以将递归关系写成 T(n) = O(1) + 2T(n - 1)。通过查找递归关系图表，我们发现 fn_a 的时间复杂度为 O(2^n)，因为在最坏情况下，会进行两次递归调用。

值得注意的是，根据大O符号的正式定义，声明fn_a的时间复杂度为O(3^n)也是正确的（尽管没什么用）。很多算法在分析时都使用了大O符号，但使用大Theta符号来收紧边界更为合适，意味着：相对于给定算法，最低、最准确的时间复杂度。

请小心，仔细阅读正式定义！

1
运行时对我的用户来说很重要。当然，大O表示法在分析“效率”方面有常数因素，因此这种方式可能与运行时间不成比例。 - doctorlove
@doctorlove，我改进了我使用的措辞。现在应该更好地传达了我的原意。 - Jacob Pollack
更好的 :-) 我仍然怀疑如果 OP 在同一台机器上运行了两个算法，时间 可能 表明代码出错，但需要进行多次实验来确定。 - doctorlove
我完全同意Jacob的观点。虽然运行时间很重要（请注意，在可能被抢占的系统中，它也不同于挂钟时间），常数因素应该减少，但复杂度符号在扩展N时更为重要，这在许多情况下是最终的关键。 - Leeor
或者你可以通过经验法则来衡量它，以获得整体情况。 - Will Ness
2
长时间运行是否意味着算法效率更低？
不一定。程序的效率不仅取决于它所需的时间，还取决于它所占用的资源。在考虑效率时还要考虑空间这一因素。
来自维基百科的解释：
为了最大化效率，我们希望最小化资源使用。然而，各种资源（例如时间、空间）不能直接比较，因此哪个算法被认为更有效往往取决于哪个效率度量被认为是最重要的，例如需要高速度还是最小内存使用或其他某些度量。
1
一般来说：是的，但当你降至1秒以下时，会有很多噪音可能会令人困惑...
运行每个测试多次，并对结果使用一些统计数据（例如平均值或平均偏差，取决于你的关心程度）
并/或让其执行更多任务-例如查找更多的质数
1
简而言之，如果您所说的效率是指时间效率，那么是的。还有内存方面的考虑。

但要小心如何衡量 - 确保您的计时工具是精确的。

请确保在没有其他程序运行的情况下在同一台机器上进行测量。
请确保多次测量并取平均值和方差以进行合理的比较。
考虑让别人审核您的代码以确保它正在执行您想要的操作。
1
算法的效率通常是通过它们处理大型输入的效率来衡量的。 1万个数字并不是一个非常大的输入，因此您可能需要使用更大的输入，然后埃拉托色尼筛法才能变得更快。

另外，您的某些实现中可能存在问题。

最后，算法的效率可以通过所需内存量来衡量（但这种度量较少见，特别是由于现在内存如此便宜）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接