當T（N）= O（2^n）時，如何計算提高CPU速度的效果？

Question

我已經介紹了以下場景：算法A是O（2^n）。我可以選擇更快的CPU 10倍，或者選擇O（n^2）的算法B.顯然我會選擇算法B，但我需要用數學來證明這一點，而不僅僅是通過推理。

我被告知算法B允許我解決（2^n/n^2）倍大的問題。這我明白。到現在爲止還挺好。但它繼續說，更快的CPU使我能夠解決問題（n + log 10）次大（大約n + 3）。

他們如何從（2^n/10）中獲得（n + log 10）？

Answer 1

解決問題所需的時間是工作量除以CPU速度，第一個算法可以表示爲（2^n）/速度。將速度乘以10，即爲（2^n）/（10 *速度）。 「允許你解決一個更大的問題」的意思是「允許你在相同的時間內解決更大的問題」。因此，（2^n）/速度=（2 ^（n +更大））/（10 *速度）。用代數的方式解決更大的問題，最終以更大的速度=速度記錄10。