Как я могу доказать по индукции, что второй из этих двух алгоритмов быстрее?

Question

У меня есть два алгоритма.

A. Solves problem in 2^n seconds. 

B. Solves problem in n^2 + 1,000,000 seconds. 

Как я могу индуктивно доказать, что B является быстрее, чем А.

Я сказал, что 2^п> 2n + 1 при п> 2 может быть полезным для этой проблемы. Я взламываю голову и не могу решить эту проблему. Благодарю.

«n» эквивалентно размеру программы.

РЕДАКТИРОВАТЬ: Для всех п> 19.

РЕШЕНИЕ:

предпосылке: п^2 + 1000000 < 2^п

Основа:
п = 20
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 всегда больше, чем А.

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 

Argh, я чувствую, что я почти там. любая помощь?

Answer 2

B будет только быстрее, если п> 19.9321. Если вам не нужна фактическая работа, то here - это то, откуда я получил ответ.

Для любых чисел, меньших 19.9321, тогда A будет быстрее.

Answer 3

Python в качестве калькулятора:

>>> n = 20 
>>> 
>>> 2**n 
1048576 
>>> n**2 + 1000000 
1000400 
>>> 

Answer 4

не знаю об использовании индукции, но я думаю, что это может быть полезно: обратите внимание, прежде всего, что логарифм является монотонно возрастающей функцией. Так, журнал (а)> журнал (б) тогда и только тогда а> B (I)

Обратите внимание, что лог (п^2)> журнал (п^2 + 1 000 000) (II)

Кроме того, журнал (п^2) = 2log (п)

ясно, nlog2> 2 LOGN при большом п, так,

 log(2^n) > log(n^2) from (i) 

так, журнала (2^п)> журнал (п^2)> log (n^2 + 1 000 000) из (ii)

поэтому,

 log(2^n) > log(n^2 + 1 000 000) 

и снова с (I)

2^n > n^2 + 1 000 000 

что вы думаете?