当T(N) = O(2^n)时，如何计算提高CPU速度的效果？

Question

我得到了以下场景:算法A是O(2^n)。我可以选择比原来快10倍的CPU，也可以选择O(n^2)的算法B。显然，我会选择算法B，但我需要从数学上证明这一点，而不仅仅是通过推理。

有人告诉我，算法B允许我解决(2^n / n^2)倍大的问题。这一点我可以理解。到目前一切尚好。

但它继续说，更快的CPU允许我解决一个(n +log10)倍于(约.N+ 3)。

他们如何从(2^n / 10)得到(n +log10)？

Answer 1

解决该问题所需的时间是工作量除以CPU速度，对于第一种算法，可以将其表示为(2^n)/speed。将速度乘以10，结果是(2^n)/(10*速度)。他们真正的意思是“允许你解决X更大的问题”是“允许你在相同的时间内解决更大的问题”。

因此，(2^n)/speed = (2^(n +较大))/ (10 *速度)。对于较大的代数求解，最终得到较大=速度log10。