Udowodnij zależność

0

Udowodnij, że n!=o(n^n)

0

Małe "o" oznacza silnie mniejszy, tzn. f(n) = o(g(n)) wtw granica ilorazu f(n)/g(n) jest zerem, zadanie polega na zastosowaniu definicji, więc za bardzo nie rozumiem pytania.

0

czyli, coś takiego nie istnieje?

0

n!<=(n/2)n/2*nn/2, a dalej już z górki

0

Ja myślę, że tam powinno być Theta. Poza tym nie lubię jak stosuje się znaki = albo !=, bo przecież o(f(n)) to zbiór funkcji, a więc powinno się stosować operator przynależności.

n! jest asymptotycznie mniejsze od c * nn, więc n! należy zarówno do O(nn) jak i o(n^n).

Aby udowodnić, że n! nie należy to Theta(nn) wystarczy jakoś przybliżyć n!, np tutaj coś jest: http://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n Potem podzielić obie strony oszacowania przez nn i pokazać, że oszacowania górne i dolne n! / n^n dążą do zera. Na końcu można zastosować twierdzenie o trzech ciągach.

0
Wibowit napisał(a)

Ja myślę, że tam powinno być Theta.

Wątpię, wtedy teza byłaby nieprawdziwa.

Wibowit napisał(a)

Poza tym nie lubię jak stosuje się znaki = albo !=, bo przecież o(f(n)) to zbiór funkcji, a więc powinno się stosować operator przynależności.

Trochę sensu w tym jest, z tym, że trzeba byłoby wprowadzić to w życie. Osobiście nie spotkałem się z definicją O(f(n)) lub o(f(n)) jako zbioru funkcji, a oznaczenie g(n) = o(f(n)) jest tylko notacją, która się dawno temu przyjęła.

0

Jak to nieprawdziwa? n! jest asymptotycznie mniejsze od nn, a g(n) \in o(f(n)) oznacza iż g(n) jest asymptotycznie mniejsze od f(n), więc n! \not\in Theta(nn). Notacja typu n! != n^n jest tylko umownym uproszczeniem, nawet Wikipedia mówi:

So the big O notation captures what remains: we write either
:<math>\ T(n)= O(n^2)</math>
or
:<math>T(n)\in O(n^2)</math>
and say that the algorithm has order of n<sup>2</sup> time complexity.
Note that "=" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is", so the second expression is technically accurate (see the "Equals sign" discussion below) while the first is a common abuse of notation.<ref name="Introduction to Algorithms">Thomas H. Cormen et al., 2001, [http://highered.mcgraw-hill.com/sites/0070131511/ Introduction to Algorithms, Second Edition]</ref>

0

Ok, słyszałem o zapisie z należeniem, ale pomyliło mi się z pewnym szczegółem.

Co do zadania, jakbyś chciał, żeby ono wyglądało z Theta? Stwierdzenie n! = Theta(n^n) jest fałszywe, a inne próby dopasowania Theta imo byłyby za bardzo na siłe włożone.

0

Oh, shit. Dobra, nieco mi się pop****liło. Myślałem, że tam jest n! != o(n^n). Sorry za niepotrzebne zamieszanie.

Ludzie, korzystajcie ze spacji czasem, bo potem nie da się zrozumieć, o co wam chodzi (w tym przypadku można by zrozumieć tak: Udowodnij, że n != o(n^n)).

0

więc tutaj należy pokazać jeszcze, że
lim n->nieskończoności n! / (n^n)=0 , tylko czy tak się da gdyż licznik i mianownik przy n dążącym do nieskończoności raczej nie dążą do zera

0

Przecież napisałem jak masz to zrobić. Na Wiki jest oszacowanie n! od góry i od dołu nie używając silni, więc możesz zbadać zbieżność ilorazu górnego oszacowania przez n^n. Wyjdzie ci 0, co potwierdzi tezę.

0

nie mogę tego znaleźć, na polskiej stronie wikipedii silnia?

0

a można na podstawie twierdzenia o 3 ciągach przedstawić tą granice, w taki sposób:

0 jest mniejsze równe n!/(n^n) jest mniejsze równe 1/n

2 skrajne dążą do 0 , więc n!/(n^n) również dąży do 0?

0

W sumie wygląda to sensownie.

0
1 * 2 * ... * n   1   2         n
--------------- = - * - * ... * -
n * n * ... * n   n   n         n

1 użytkowników online, w tym zalogowanych: 0, gości: 1