Решение задачи в книге Кормена "Алгоритмы. Построение и анализ"

Question

Решение задачи в книге Кормена "Алгоритмы. Построение и анализ"

Рейтинг: 4Ответов: 2Опубликовано: 20.04.2023

Делаю задания в книге Кормена "Алгоритмы. Построение и анализ". Не могу понять один момент в такой вот задаче на странице 86, подпункт е:

В ответах для А=lg(n!) и B=lg(n^n) в случае о(о малое) написано, что - нет. Хотя у меня получается ответ - да. Я пользуюсь формулой из книги, чтобы доказать, что lg(n!)=o(lg(n^n)):

0 <= lg(n!) < c * lg(n^n).

Т.к. lg(n!) <= lg(n^n) при n > 1. То при любой c: lg(n!) <= c * lg(n^n). Получается, что lg(n!)=o(lg(n^n)). Но я смотрел ответы в разных источниках, и там написано что это не так. Объясните, пожалуйста, в чём я не прав.

математика

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

lg(n!) = ∑_1≤i≤nlg(i) ≥ _{(оставляем только старшую половину суммы)}

≥ ∑_n/2≤i≤nlg(i) ≥ _{(оценка элементов снизу)}

≥ ∑_n/2≤i≤nlg(n/2) = _{(сворачиваем сумму)}

= (n/2)lg(n/2) = _{(выделяем из суммы nlg(n))}

= (n/2)(lg(n) - lg(2)) = (n/2)(lg(n)(1 - lg(2)/lg(n))) = ((1 - lg(2)/lg(n))/2) n·lg(n) ≥

_{(вводим константу C = (1 - lg(2)/lg(n₀))/2)}

≥ C·n·lg(n)

Последнее неравенство верно начиная с любого n₀ > 2.

То что lg(n!) ≤ lg(nⁿ) (логарифм факториала растёт не быстрее логарифма степени) вы уже знаете. Выше доказана обратная оценка - логарифм степени растёт не быстрее логарифма факториала.

Правильный ответ - θ.

Answer 2

▲ 4

Есть такая формула Стирлинга:

Откуда, думаю, все сразу же становится очевидным :)

Если рассмотреть отношение логарифмов n! и nⁿ, то предел такого отношения равен 1.

Решение задачи в книге Кормена &quot;Алгоритмы. Построение и анализ&quot;

Ответы

Решение задачи в книге Кормена "Алгоритмы. Построение и анализ"