Если взять k = 0, то n> 1, то после этого я умножаю обе стороны на n^(n-1) .. , поэтому он становится n^n> n^(n-1) .. но I не может найти n! здесь, чтобы получить свидетелей .. Пожалуйста, помогите !!Как я могу найти свидетеля отношения n! O (n^n)?
На самом деле O(n!) является менее чем O(n**n) так
O(n!) = O(n**n * sqrt(n)/exp(n))
который может быть получен из Стирлинга приближения:
Также из Wiki: ['Утверждение f (n) = O (n!) Иногда ослабляется к f (n) = O \ left (n^n \ right), чтобы получить более простые формулы для асимптотической сложности. Для любого k> 0 и c> 0 O (n^c (\ log n)^k) является подмножеством O (n^{c + \ varepsilon}) для любого \ varepsilon> 0, поэтому его можно рассматривать как полином с некоторым большим порядком.] (https://en.wikipedia.org/wiki/Big_O_notation) Лучше всего посмотреть на Wiki из-за специальных символов ... –
Но как я могу доказать это отношение через свидетелей? ? Как я уже упоминал подробно, я не смог найти свидетелей. –
@FahadRehman Вам, вероятно, было бы лучше спросить об этом на http://math.stackexchange.com/ –
Добро пожаловать на переполнение стека! См. [Ask] и [mcve]. [edit] вопрос добавить более подробную информацию, код и т. д. – Tushar
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что это математический вопрос, а не вопрос программирования. – MikeCAT
'O (n!) = O (n ** n/exp (n) * sqrt (n))' –