我有两个算法。
A. Solves problem in 2^n seconds.
B. Solves problem in n^2 + 1,000,000 seconds.
我怎么能归纳地证明b比a快。
我听说2^n>2n+1对于n>2可能有用。我一直在绞尽脑汁,解决不了这个问题。感谢
“n”等于程序的大小。
编辑:所有n>19。
解决方案:
前提:n^2+1000000<2^n
依据:
n=20个
1000400归纳:
(n+1)^2 + 1000000 > 2^(n+1)
n^2 +2n +1 +1000000 > 2^(n+1)
Apply 2^n > 2n + 1
n^2 + 1000000 > 2^(n+1)
最后一行表示B总是大于A。
最佳答案
正如你所说,基本情况已经证明。
iek^2<2^k for k>=5
对于归纳法,我们假设
k^2<2^k
我们需要证明
(k+1)^2<2^(k+1)
(k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1
我们知道
(k-1)^2>=0.
因此k^2>=2k-1
2^k + 2k + 1 = 2^k + 2k -1 + 2 <= 2^k + k^2 + 2 < 2^k + 2^k +2= 2^(k+1) + 2
啊,我觉得我快到了。有什么帮助吗?