Nieskończony łańcuch dużych

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

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ takie, że $0\le f(n)\le cg(n), \forall n\ge n_0$

Powiedzmy, że mamy skończoną liczbę funkcji: $f_1,f_2,\dots f_n$ spełniające:

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

Przez przechodniość $O$ mamy to: $O(f_1)\subseteq O(f_n)$

Czy to chwyt jeśli mamy nieskończony łańcuch $O's$ ? Innymi słowy, czy $O(f_1) \subseteq O(f_\infty)$ ?

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

asymptotics landau-notation

— saadtaame
źródło

Odpowiedzi:

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 mamy . Taka sekwencja może nie mieć ostatniej funkcji. $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ $i$ $f_i(n) = O(f_{i+1}(n))$

$f_\infty(n) = \lim_{i\to \infty} f_i(n)$ $f_1(n) = O(f_\infty(n))$ $f_i(n) = \frac{n}{i}$ $i$ $f_i(n)=\Theta(n)$ $f_i(n) = O(f_{i+1}(n))$ $f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$ $f_1(n) \neq O(f_\infty(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órych $f_i \in \mathcal O(f_{i+1})$ $\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$ $f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$ $j$ $\mathcal O(f_i), i \ge n_0$ $n_0$ (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

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_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

— 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

@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_{\infty}

$f_\infty$

— frafl

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) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x)$

O (e^{x}) \subseteq O (x e^{x}) \subseteq O (e^{2 x}) \subseteq O (e^{e^{x}}) \subseteq \dots

$O(\mathrm{e}^x) \subseteq O(x\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

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)$ $\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (\frac{e^{x}}{x^{2}}) \subseteq O (\frac{e^{x}}{x}) \subseteq O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x)$

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. $f_1, \ldots, f_n$ $f_\infty$ $f_i$ $\mathbb{N}$ $\mathbb{R}_+$ $f_\infty(x) = \max \{f_n(x) \mid n \in\mathbb{N}\}$ $\{f_n(x) \mid n \in\mathbb{N}\}$

f_{\infty} (x) = max {f_{n} (x) ∣ 1 \leq n \leq N} if N \leq x < N + 1

$f_\infty(x) = \max \{f_n(x) \mid 1 \le n \le N \} \qquad \text{if $N \le x \lt N+1$}$ Następnie dla dowolnego , , ponieważ . Jeśli chcesz, aby funkcja rosła szybciej ( ), weź .

N

$N$

f_{N} \in O (f_{\infty})

$f_N \in O(f_\infty)$

\forall x \geq N, f_{\infty} (x) \geq f_{N} (x)

$\forall x \ge N, f_\infty(x) \ge f_N(x)$

f_{\infty} = o (f_{\infty}^{'})

$f_\infty = o(f_\infty')$

f_{\infty}^{'} (x) = x \cdot (1 + f_{\infty} (x))

$f_\infty'(x) = x \cdot (1 + f_\infty(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 ?)

@ 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”