Udowodnij zależność

Odpowiedz Nowy wątek
2011-10-14 15:02
0

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

a co to jest o? - Rev 2011-10-14 15:37
praca domowa? rozumiesz w ogóle co napisałeś? - rafal__ 2011-10-14 15:51
Jeżeli (jak przypuszczam) o oznacza mniejszy lub równy w granicy, to jest to trywialne. (O ile się wie, że liczby 1,...,n-1 są mniejsze od n). - bogdans 2011-10-14 16:01

Pozostało 580 znaków

2011-10-14 16:29
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.

Pozostało 580 znaków

2011-10-14 17:00
0

czyli, coś takiego nie istnieje?

edytowany 1x, ostatnio: DBest, 2011-10-14 17:00

Pozostało 580 znaków

2011-10-14 17:01
0

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


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2011-10-14 23:41
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/[...]nd_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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-10-15 16:42
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.

edytowany 2x, ostatnio: XnaP, 2011-10-15 17:18

Pozostało 580 znaków

2011-10-15 23:45
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>


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-10-15 23:47

Pozostało 580 znaków

2011-10-16 03:14
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.

Pozostało 580 znaków

2011-10-16 10:29
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)).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Chwila zastanowienia nad wzorem, i nie można tak zrozumieć (bo to oczywiście oczywista nieprawda). - bogdans 2011-10-16 11:23
No toż właśnie pomyślałem, że wzór źle przepisany. - Wibowit 2011-10-16 11:29
Ja tak zrozumiałem na początku i też się zastanawiałem o co chodzi. Morał - używać spacji. - msm 2011-10-16 20:00

Pozostało 580 znaków

2011-10-16 19:46
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

Pozostało 580 znaków

2011-10-16 19:50
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ę.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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