докажи что п!= O (n ^ n)

Question

Обновление: Извините, я забыл положить n ^ n внутри O ()

Моя попытка была решить эту рекуррентную связь:

T(n) = nT(n-1) +1
T(0) = 1;

Используя метод итерации, я получил n ^ n, но я не уверен, что это способ доказать это.

Answer 1

Я предполагаю, что вы хотите доказать, что функция n! является элементом множества O(n^n).Это легко доказать:

Определение: функция f(n) является элементом множества O(g(n)), если существует c>0, такое, что существует m, такое что для всех k>mу нас это f(k)<=c*g(k).

Итак, мы должны сравнить n! с n^n.Давайте напишем их один под другим:

n!  = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
n^n = n *  n    *  n    *  n    * ... * n * n * n

Как видите, первая строка (n!) и вторая строка (n^n) имеют ровно n элементов с правой стороны.Если мы сравним эти элементы, то увидим, что каждый элемент имеет максимальный размер, соответствующий соответствующему элементу во второй строке.Таким образом n! <= n^n (по крайней мере, для n> 5).

Итак, мы можем - посмотрим на определение - скажем, что существует c=1 такое, что существует m=5 такое, что для всех k>5 у нас есть это k! < k^k, что доказывает, что n! действительно является элементом O(n^n).

Answer 2

Примечание: Ниже приведен ответ на оригинальный вопрос: «Докажите, что n! = N ^ n»

Я могу доказать, что это не правда довольно легко: возьмите n = 5.

n! = 120
n^n = 3125

Answer 3

Это не правда, что n!= n ^ n, и поэтому вы не сможете доказать это.Кроме того, решение вашего рекуррентного отношения не является ни n!или п ^ п.(Он удовлетворяет T (1) = 1 * 1 + 1 = 2, что не равно ни 1! Ни 1 ^ 1.)

Что именно вы пытаетесь сделать и почему?

Answer 4

n! != n^n. Однако последовательность T(n), определенная выше, не является n!. Но равно ли оно n^n? Для n=1, T(1) = 1*T(0) + 1 = 1*1 + 1 = 2, но n^n = 1^1 = 1. Однако, если вы также имели в виду T(1) = 1, то они равны n=1. Идем дальше, для n=2, затем T(2) = 2*T(1) + 1 = 2*1 + 1 = 3! = 2^2. Поэтому я, честно говоря, не уверен, что вы пытаетесь спросить.

Answer 5

для n==2, n! = 2 != 4 = n^n.
для n!=2, (n-1) делит n!, но n-1 не делит n^n (n^n mod n-1 == 1)

Фактическое приближение перемешивания составляет n! ~ sqrt(2 Pi n) (n/e)^n

Какое у вас математическое образование? Вы хотите сложное аналитическое доказательство или что-то более комбинаторное по своей природе?