Сложность доказательства

Я хотел бы, чтобы доказать следующий пример:Сложность доказательства

n^k = O (c^n) for every k and c>1

Заметно, что полиномиальная функция растет быстрее, чем экспоненциальная функция. Мы пытаемся найти k0> 0, удовлетворяющих условию

fn > = k0 * g(n)

Чем

n^k <= k0 * c^n 
log(n^k) <= log (k0 * c^n) 
log(n^(k/n)) <= log (k0 * c) 
k0 >= 1/c*n^(k/n)

Итак, k0> 0, положительны и достаточно малы, в то время как значение с не имеет никакого отношения ... это нормально?

источник

2010-10-05 Ian

Не теряя времени, чтобы написать это, шаг 3 беспокоит меня, я не уверен, что вы можете сделать это с помощью журналов. (обратите внимание на статью Лампорта о доказательствах, которую стоит прочитать). –

Пол прав, вы не можете сделать это с помощью журналов в шаге 3. log (c^n) = n * log (c). Поэтому шаг 3 должен быть: (log (n^k))/n <= log (k0 * c) – mpd

Thanx, на шаге 3 есть ошибка, я быстро написал и не проверял. – Ian

log(n^k) <= log (k0 * c^n) 
k log n <= log k0 + n log c 

k log n - n log c <= log k0 
log (n^k) - log (c^n) <= log k0 
log ((n^k)/(c^n)) <= log k0 | expo 
(n^k)/(c^n) <= k0 
n^k <= k0 * c^n 

=> n^k = O(c^n)

Ваш шаг 3 кажется неправильным, по крайней мере, я не вижу, откуда вы его взяли. Ваш вывод также не доказывает того, о чем просили.

источник

2010-10-05 20:58:17 IVlad

ответ

Смежные вопросы