假设特定算法所需的操作数恰好为 T(n) = 2^n 并且我们的 1.6 Ghz 的计算机每秒执行 16 亿次操作。最大的是什么 就 n 而言,可以在一秒钟内解决的问题?不到一天?
我累了一秒2^1.6和2^(1.6*60*24),但我想我误解了这个问题。
最佳答案
我们知道的:
- 要在 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 的问题所需的时间...
关于算法:T(N) =2^N,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55643843/