6

我试图比较两种算法的运行速度：一个用于打印素数（10,000 个数字）的蛮力 C 程序，以及一个埃拉托色尼筛法 C 程序（也是 10,000 个素数）。

我测量的筛算法运行时间是：0.744 秒

我测量的蛮力算法的运行时间是：0.262 秒

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

因此，我的问题是：由于我得到了与我预期相反的结果，这是否证明 Eratosthenes 筛在速度方面确实是效率较低的算法，与试验划分相比？

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

4

6 回答 6

7

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

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

因此，即使在某些输入处code_1运行速度比 快10倍code_2，但它的运行时间随着输入大小的每翻倍而翻倍，而对于它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对于 Eratosthenes 的筛子，它O(n log n log (log n))通常被视为~ n^1.1..1.2。但是，试验部门和 Eratosthenes 的筛子肯定存在次优的实现，它们的运行情况~n^2.0甚至更糟。

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

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

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

于 2013-08-21T05:17:37.353 回答
6

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

效率通常分为两个小节：

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

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

请注意，我附上了 Big Oh 符号的链接——姐妹符号都可以在该 Wikipedia 页面上找到，它通常是一个很好的起点。它也将涉及空间和时间效率的差异。

使用 Big 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))]))

...我们看到：empty?、rest和都是 O(1) >。first我们还注意到，在最坏的情况下，会在offn_a的第三个条件和第四个条件下调用。然后我们可以将递归关系写为 T(n) = O(1) + 2T(n - 1)。在递归关系图上查看它，我们看到它的顺序为 O(2^n)，因为在最坏的情况下，会进行两次递归调用。restinput_afn_a

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

小心，阅读正式的定义！

于 2013-08-16T09:30:58.543 回答
2

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

不必要。程序的效率不仅由它所花费的时间来衡量，而且由它所占用的资源来衡量。空间是考虑效率时要牢记的另一个因素。

来自维基：-

为了获得最大效率，我们希望尽量减少资源使用。然而，各种资源（例如时间、空间）不能直接比较，因此两种算法中的哪一种被认为更有效通常取决于哪种效率度量被认为是最重要的，例如对高速的要求，或最小内存使用量，或其他一些措施？

于 2013-08-16T09:38:46.883 回答
1

算法的效率通常通过它们处理大量输入的效率来衡量。10,000 个数字并不是一个很大的输入，因此在 Eratosthenes 的筛子开始变得更快之前，您可能需要使用一个更大的数字。

或者，您的一个实现中可能有一个大问题

最后，算法的效率可以通过所需的内存量来衡量（但这种衡量标准不太常见，尤其是现在内存如此便宜）

于 2013-08-16T09:35:44.543 回答
1

一般来说：是的，但是当你在低于 1 秒的范围内时，会有很多噪音可能会让人困惑......

多次运行每个测试并在结果中使用一些统计数据（例如平均值或平均值/偏差，具体取决于您关心的程度）

和/或让它做更多的工作——比如找到更多的素数

于 2013-08-16T09:30:02.050 回答
1

简而言之，是的，如果效率是指时间效率。还有内存方面的考虑。

不过要小心你的测量方式——确保你的计时工具是精确的。

确保在没有其他设备运行时在同一台机器上进行测量。
确保您测量了几次并取平均值和方差进行比较。
考虑让某人检查您的代码以检查它是否正在执行您认为它正在执行的操作。

于 2013-08-16T09:30:31.127 回答