我试图比较两种算法的运行速度:一个用于打印质数(10,000个数字)的蛮力C程序和一个Eratosthenes C程序筛网(也包含10,000个质数)。
我为筛子算法测得的运行时间为:0.744秒
我为蛮力算法测得的运行时间为:0.262秒
但是，有人告诉我，Eratosthenes算法的“筛选”比“蛮力”方法更有效，因此我认为它的运行速度会更快。所以我错了或者我的程序有缺陷(对此我表示怀疑)。
因此，我的问题是:由于得到的结果与预期相反，因此是否证明了Eratosthenes的Sieve在速度方面的确比在试验方面效率更低？
我不确定是否相关，但是我使用的是Dev C++编译器和Windows 7。
最佳答案
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。但是，肯定有试验部门和Eratosthenes筛子在~n^2.0或更低版本上运行的次佳实现。
因此，否，什么都没有证明。一个数据点毫无意义，至少需要三个数据点才能获得“全局”，即可以确定地预测较大输入大小所需的运行时间⁄空间。
scientific method的目的在于确定性地进行预测。
顺便说一句，您的运行时间很长。 10,000个质数的计算应该几乎是瞬时的，对于在快速框上运行的C程序而言，它的秒数要不到1/100秒。也许您也在测量打印时间。别。 :)