我有两种算法。
A. Solves problem in 2^n seconds.
B. Solves problem in n^2 + 1,000,000 seconds.
我如何归纳证明B 比 A 快。
有人告诉我 2^n > 2n+1 for n>2 可能对这个问题有用。我一直在绞尽脑汁，无法解决这个问题。谢谢。
“n”相当于程序的大小。
编辑：对于所有 n > 19。
解决方案：
前提：n^2 + 1,000,000 < 2^n
基础：
n = 20
1000400 < 1048576 真
就职：
(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。
只有当 n > 19.9321 时，B 才会更快。如果您不需要实际工作，那么这就是我得到答案的地方。
对于任何小于 19.9321 的数字，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
啊，我觉得我快到了。有什么帮助吗？
Python作为计算器：
>>> n = 20
>>>
>>> 2**n
1048576
>>> n**2 + 1000000
1000400
>>>