Nieskończony łańcuch dużych

12

Po pierwsze, pozwól mi napisać definicję dużego O tylko po to, żeby coś wyjaśnić.

f(n)O(g(n))c,n0>0 takie, że0f(n)cg(n),nn0

Powiedzmy, że mamy skończoną liczbę funkcji: f1,f2,fn spełniające:

O(f1)O(f2)O(fn)

Przez przechodniość O mamy to: O(f1)O(fn)

Czy to chwyt jeśli mamy nieskończony łańcuch Os ? Innymi słowy, czy O(f1)O(f) ?

Mam problem z wyobrażeniem sobie, co się dzieje.

saadtaame
źródło

Odpowiedzi:

15

Najpierw musimy wyjaśnić, co rozumiemy przez „czy to obowiązuje, jeśli mamy nieskończony łańcuch?”. Interpretujemy to jako nieskończoną sekwencję funkcji tak że dla wszystkich i mamy f i ( n ) = O ( f i + 1 ( n ) ) . Taka sekwencja może nie mieć ostatniej funkcji.{fi:NN1i}ifi(n)=O(fi+1(n))

f(n)=limifi(n)f1(n)=O(f(n))fi(n)=niifi(n)=Θ(n)fi(n)=O(fi+1(n))f(n)=limifi(n)=0=Θ(1)f1(n)O(f(n))

Z drugiej strony możemy spojrzeć na granicę sekwencji klas, która nie musi być równa klasie granicy funkcji . Mamy , dlatego i dla wszystkich . Limit przełożony zawiera wszystkie elementy (w tym przypadku funkcje), które występują nieskończenie często, a limit podrzędny zawiera wszystkie elementy, które występują we wszystkich dla niektórychfiO(fi+1)O(fi)O(fi+1)fjlimiO(fi)=lim supiO(fi)=lim infiO(fi)=nNk>nO(fk)jO(fi),in0n0 (które może zależeć od elementu). Ponieważ sekwencja klas rośnie monotonicznie, obie istnieją i są one równe. Uzasadnia to użycie .lim

Frafl
źródło
3
Istnieją dwie serie: jedna z funkcji (które mogą się zbiegać lub nie) i jedna ze zbiorów (gdzie każdy zestaw jest super zestawem poprzedniego; dlatego ta seria jest zbieżna - patrz definicja lim inf i lim sup dla zbiorów) . Pierwsza część odpowiada na pytanie bez części , druga część odpowiada negatywnie na część (jeśli jest jakąś limonką). f f fff
frafl
Co jeśli liczba warunków jest niepoliczalna? :)
SamM
Korzystając z porządnego zamówienia, czy chcesz zastąpić serię czymś bardziej ciągłym? :)
frafl
@Kaveh Wielkie dzięki, teraz ma to sens. Jeśli mógłbyś uzasadnić użycie limitów i co to oznacza, to to uzupełni moje zrozumienie.
saadtaame
1
@saadtaame: Może to dlatego, że powyższe pytanie wciąż nie pyta, co chcesz wiedzieć? Jeśli dobrze pamiętam, dodałeś powodu sugerowanego komentarza. Jeśli podasz jakiś kontekst, być może ktoś może ponownie sformułować pytanie. f
frafl
5

Tak, możliwe jest posiadanie nieskończonego łańcucha.

Jestem pewien, że znasz już kilka przykładów: Tutaj masz nieskończony łańcuch: wielomiany rosnącego stopnia. Czy możesz pójść dalej? Pewnie! Wykładniczy rośnie szybciej (mówiąc asymptotycznie) niż jakikolwiek wielomian. I oczywiście możesz kontynuować:O ( x ) O ( x 2 ) O ( x 42 ) O ( e x ) O ( e x ) O ( x

O(x)O(x2)O(x42)
O(x)O(x2)O(x42)O(ex)
O(ex)O(xex)O(e2x)O(eex)

Możesz zbudować nieskończony łańcuch również w innym kierunku. Jeśli to (trzymanie się funkcji dodatnich, ponieważ tutaj omawiamy asymptotykę funkcji złożoności). Mamy więc na przykład:f=O(g)1g=O(1f)

O(x)O(x2)O(exx2)O(exx)O(ex)

W rzeczywistości, biorąc pod uwagę dowolny łańcuch funkcji , możesz zbudować funkcję która rośnie szybciej niż wszystkie z nich. (Zakładam, że to funkcje od do .) Najpierw zacznij od pomysłu . To może nie działać, ponieważ zbiór może być nieograniczony. Ale ponieważ jesteśmy zainteresowani jedynie asymptotycznym wzrostem, wystarczy zacząć od małego i stopniowo się rozwijać. Weź maksimum nad skończoną liczbą funkcji. f1,,fnffiNR+f(x)=max{fn(x)nN}{fn(x)nN} N f NO ( f ) x N , f ( x ) f N ( x ) f = o ( f ) f ( x ) = x ( 1 + f ( x ) )

f(x)=max{fn(x)1nN}if Nx<N+1
Następnie dla dowolnego , , ponieważ . Jeśli chcesz, aby funkcja rosła szybciej ( ), weź .NfNO(f)xN,f(x)fN(x)f=o(f)f(x)=x(1+f(x))
Gilles „SO- przestań być zły”
źródło
Wszystkie te odpowiedzi (twoje i inne) oparte są na założeniu, że wiemy, co dzieje się w nieskończoności, nie są dla mnie zadowalające, nie wiem o OP (dlaczego nie powinniśmy mieć zamkniętej grupy o nieskończonej wielkości ?)
4
@ SaeedAmiri Przykro mi, nie rozumiem twojego komentarza: co rozumiesz przez „wiemy, co dzieje się w nieskończoności, nie są dla mnie zadowalające”?
Gilles „SO- przestań być zły”