如果我知道算术复杂性，我可以计算程序运行所需的时间吗?

Question

我目前正在做一个用费马小定理寻找素数的任务(这是强制性的(，我拥有的程序(我认为(具有复杂性O(logn(。然而，对于非常大的数字，它拖得太多了(我们谈论的是 1200 位数字，该类的大小(，比如 8 分钟 ，我不知道这是否正常。有没有办法在我们知道复杂性的情况下计算输入的平均时间？

Answer 1

如果你的算法具有渐近时间复杂度f(n(，这告诉你的是lim T(n+1(/T(n( = lim f(n+1(/f(n(，因为n去无穷大。因此，如果您知道 N、f 和 T(N(，并且如果 N 已经足够大以至于渐近行为近似，那么您可以估计 T(N+1( = T(N( * f(N+1(/f(N(。要选择足够大的 N，您需要了解所涉及的常数因素。