画家难题 - 从第一原理进行算法估计

这个问题是基于从2001年开始。

A guy “找到了一份街头油漆工的工作，在路中间画虚线。”第一天他完成了 300 码，第二天完成了 150 码，第三天甚至更少。老板很生气，要求一个解释。

“我无能为力，”那家伙说。“我每天都离油漆罐越来越远！”

我的问题是，你能估计一下他第三天走了多少距离吗？

链接线程中的评论之一确实得出了精确的解决方案，但我的问题是关于一个足够好的解决方案估计——比如说 10%——根据一般原则，这很容易得出。

澄清：这是关于算法分析中的某种方法，not关于开发算法，也不是代码。

这里有很多未知数——他的行走速度、他的绘画速度、画笔中的颜料能持续多久……

但显然这里正在进行两个过程。一种是二次的——它是油漆罐和绘画点之间的来回行走。另一个是线性的——它是绘画的过程本身。

考虑到第 10 天甚至第 100 天，很明显线性分量变得可以忽略不计，并且该过程变得非常接近二次方 - 步行几乎花费了所有时间。相反，在第一天的前几分钟，它接近于线性。

因此我们可以说，时间t作为距离的函数s遵循幂律t ~ s^a具有变化的系数a = 1.0 ... 2.0。这也意味着s ~ t^b, b = 1/a.

应用经验增长阶数分析 http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth:

The b第 1 天和第 2 天之间的系数近似为

    b(1,2) = log (450/300) / log 2 = 0.585     ;; and so,
    a(1,2) = 1/b(1,2) = 1/0.585 = 1.71

正如预期的那样，a系数低于2。对于第2天和第3天之间的时间段，我们可以将其大约设置为之间的中间值1.71 and 2.0,

    a(2,3) = 1.85                    ;; a = 1.0 .... 2.0
    b(2,3) = 0.54                    ;; b = 1.0 .... 0.5
    s(3)   = s(2) * (3/2)^b(2,3)
           = 450 * (3/2)^0.54
           = 560 yards

因此第三天行驶的距离可以估计为560 - 450 = 110 yards.

如果a系数具有最大可能值，2.0，已经（这是不可能的）？然后，450*(3/2)^0.5 = 551码。而对于另一个极端，如果是一样的话1.71（这显然也不可能），450*(3/2)^0.585 = 570.

这意味着 110 码的估计是合理的，两侧误差均小于 10 码。