如何从 Big-O 表示法找到运行时间？

Question

当只给定函数的输入大小和 Big-O 表示法时，我很难理解如何找到函数的准确运行时间。有人可以解释如何解决以下示例问题吗？

输入大小为 100 时，算法需要 0.5 毫秒。如果运行时间如下（假设低阶项可以忽略不计），则输入大小为 500 需要多长时间？
A。线性
b. O(N logN)
C。二次
d.立方

Answer 1

简而言之，您将相对执行时间视为相对输入大小的适当函数，并根据算法的假设复杂性选择“适当的函数”。

具体来说，线性算法的执行时间将作为相对输入大小的线性函数缩放，二次算法的执行时间与输入大小成二次函数缩放，等等。

在此示例中，您知道算法在输入大小 100 上执行需要 0.5 毫秒，如果您想知道它在输入大小 500 上的执行情况，您问自己的第一个问题是“输入大小的相对变化是多少？” ' （即“由于什么因素而改变？”）答案 = new_size/old_size = 500/100 = 5：输入增大了 5 倍。

接下来，为了确定（估计）新的执行时间，您可以根据算法假设的复杂性对此比例因子和原始执行时间应用适当的函数。让我们为新的执行时间 T 调用该函数，将初始时间表示为 t_0，输入比例因子表示为 f。您可以使用假设的复杂性来评估 T 以获得新的执行时间：

Linear:       T(f,t_0) = (f)t_0      = (5)0.5ms       = 0.25ms 
Linearithmic: T(f,t_0) = flog(f)t_0  = (5log(5))0.5ms = 0.58ms (assuming base 2)
Quadratic:    T(f,t_0) = (f^2)t_0    = (5^2)0.5ms     = 1.25ms
Cubic:        T(f,t_0) = (f^3)t_0    = (5^3)0.5ms     = 62.5ms

您可以将此方法推广到其他情况，在这些情况下，您希望根据假设的复杂性和有关某些输入上的执行时间的数据点来估计算法在新输入大小上的执行时间，方法是计算新的比例因子“f”和插入 t_0 的已知时间。

Answer 2

抱歉让您困惑了，为什么线性计算不是 2.5 毫秒？