这个问题是基于2001年的Joel Spolsky的一个难题。
一个人 “找到了一份街头画家的工作,在路中间画了虚线。” 在第一天,他完成了300码,在第二天达到了150码,在第三天则更少。老板很生气,要求解释。
__那家伙说: “我 无能为力。” “每天我都离油漆罐越来越远了!”
我的问题是,你能估计他第三天的距离吗?
链接线程中的注释中的一个确实得出了精确的解决方案,但是我的问题是关于足够精确的估计(例如10%),这很容易从一般原则中得出。
这里有很多未知数-他的步行速度,绘画速度,刷子中的油漆能持续多久…
但是显然这里有两个过程。一个是平方的-是在油漆罐和油漆点之间来回走动。另一个是线性的-这是绘画的过程本身。
考虑到第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) 的 经验顺序 :
第1天和第2天之间的 b 系数近似为
b(1,2) = log (450/300) / log 2 = 0.585 a(1,2) = 1/0.585 = 1.71
正如预期的那样,该系数低于2。对于介于第2天和第3天之间的时间段,我们可以将其大约设置为介于 1.71 和 2.0 之间的中间值,
a(2,3) = 1.85 b(2,3) = 0.54 450*(3/2)**0.54 = 560 yards
因此,第三天的距离可以估计为560 - 450 = 110码。
560 - 450 = 110
如果 a 系数已经具有最大可能值 2.0 怎么办(这是不可能的)?然后,450*(3/2)**0.5 = 551码。而对于另一个极端,如果是相同的 1.71 (这显然是不可能的,要么), 450*(3/2)**0.585 = 570。
450*(3/2)**0.5 = 551
450*(3/2)**0.585 = 570
这意味着110码的估计值是合理的,任一侧的误差均小于10码。