performance - 我如何通过归纳法证明这两种算法中的第二种算法更快？

Question

我有两种算法。

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。

Answer 1

正如您所说，基本案例已得到证明。即k^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

啊，我觉得我快到了。有帮助吗？