处理器速度呈指数级增长

Question

根据 Exponential growth

上的维基百科文章

E.g. if a slow processor can solve problems of size x in time t, then a processor twice as fast could only solve problems of size x+constant in the same time t.

我的问题是，我们如何计算添加到尺寸 x 的常数值。我看过许多描述 growth 的页面，但没有介绍如何计算此常量。有什么想法吗？

谢谢，

Answer 1

条目说的是这样的。假设该算法是基数为 c 的指数算法，因此对于大小为 x 的某些输入，运行 时间为

t ~= c^x.

现在给定一个速度两倍的处理器，输入只是 a（我称你的常量为）更大，时间将再次是

t ~= 0.5 c^{x + a}.

后者除以前者，我们得到

1 ~= 0.5 c^a

或者，求解常数 a，

a ~= loc_c(2).

---

不要把这些东西看得太严格。增长项的顺序仅表示这些项 支配 函数。因此大约。上面的标志。