算法:T(N) =2^N

Question

假设特定算法所需的操作数恰好为 T(n) = 2^n 并且我们的1.6 Ghz 的计算机每秒执行 16 亿次操作。最大的是什么就 n 而言，可以在一秒钟内解决的问题？不到一天？

我累了一秒2^1.6和2^(1.6*60*24)，但我想我误解了这个问题。

Answer 1

我们知道的:

• 要在 1 秒内执行少于 1.6*10^9 次操作
• 所需的操作数是 T(n)=2^n，n 是问题的大小

我们正在寻找最大值 n(1 秒内问题的最大大小)。所以我们可以这样写:

2^n <= 1.6*10^9 
n <= ln(1.6*10^9) / ln(2)
n <= 30

So in one sec you can compute a problem of size 30

现在 1 天是 24 * 60 * 60 秒，所以:

2^n <= 86400 * 1.6*10^9 
n <= ln(86400 * 1.6*10^9)/ln(2)
n <= 46

So in one day you can compute a problem of size 46

想象一下解决一个大小为 64 的问题所需的时间...