私には2つのアルゴリズムがあります。
A. Solves problem in 2^n seconds.
B. Solves problem in n^2 + 1,000,000 seconds.
BがAよりも速いことを帰納的に証明するにはどうすればよいですか。
この問題には、n>2の場合は2^ n> 2n+1が役立つ可能性があると言われています。私は頭を割っていて、この問題を解決することはできません。ありがとう。
「n」はプログラムのサイズに相当します。
編集：すべてのn>19の場合。
解決：
前提：n ^ 2 + 1,000,000 <2 ^ n
基準：
n = 20
1000400 <1048576 TRUE
誘導：
(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よりも大きいことを意味します。
Bは、n>19.9321の場合にのみ高速になります。実際の作業が必要ない場合は、ここから回答を得ました。
19.9321未満の数値の場合、Aの方が高速になります。
あなたが言ったように、ベースケースは証明されています。すなわち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
ああ、もうすぐです。何か助けはありますか？
計算機としてのPython：
>>> n = 20
>>>
>>> 2**n
1048576
>>> n**2 + 1000000
1000400
>>>