algorithm - 使用 Rabin-Miller 实现查找大 O 符号

Question

我有一个关于尝试为我已经实现的 Rabin-Miller 算法决定大 O 符号的问题。

当生成一个

 512 bits prime, I get a runtime of   22 seconds,
1024 takes                           237 seconds,
2048 takes                          2942 seconds.

如何确定这些值的大 O 表示法？在我看来，每当位大小增加 2 时，运行时间就会增加 大约 10 倍。这是否意味着它是 O(10n)？

Answer 1

您太少点来估计实验的函数(以及 O(function))。

   x | f(x)
-----------
 512 |   22
1024 |  237
2048 | 2942

如果我们测试 O(n)(O(10n) 实际上是 O(n))作为 f( x) = Ax + B 借助 Least Squares 进行猜测方法，我们会得到一个很好的拟合

A =     2.0
B = -1330.5
R =     0.964   (Correlation)

但是，许多替代函数具有更好支持

f(x) = Ax**4 + B  with correlation R = 0.99990 <- actual best fit
f(x) = Ax**3 + B         -/-       R = 0.99937 <- expected
f(x) = Ax**2 + B         -/-       R = 0.99232

你想要更多的点来找出正确的函数:当只有三个值时Ax**4 + B(对应于O(x**4)) 是目前的领导者，但我们不能拒绝 expected complexity即 Ax**3 + B。

最后，我们可以猜测(我们不能仅用三点得出结论)实现次优:O (x**4) 而不是预期的 O(x**3)

如果我们的猜测 O(x**4) 是正确的，那么我们可能会期望加倍 x:x -> 2 * x 我们将时间增加 16 倍 (2**4 == 16)