Matematické Fórum

Andrejka3

Dobrý den.
Mohl by mi někdo poradit, prosím?
Srovnejte následující fce podle rychlosti růstu (v nekonečnu):
$n \ln n, (\ln \ln n)^{\ln n}, (\ln n)^{\ln \ln n}, ne^{\ln n}, (\ln n)^{\ln n}, n2^{\ln \ln n},n^{1+1/{\ln n}}, n^2$ .
Ráda bych jako výsledek dostala tabulku, kde by například fce, která by byla výše rostla řádově rychleji než ty níže. A nějak porovnat ty, které rostou podobně rychle.
Určitě je třeba
$n^{1+1/{\ln n}}=o(n \ln n), n \ln n = o(n^2)$ .
Navrhuji použít tyto definice:
$f=o(g) \iff \lim \frac{f}{g}=0$
$f=O(g) \iff \exists \text{ okolí } U, \exists C \in R: |f| \leq C|g| \text{ na okoli }U$
$f \sim g \iff \lim \frac{f}{g} \in \mathbb{R} \setminus \{0\}$
$f \approx g \iff \lim \frac{f}{g}=1$ .

Moc mi nejde vyšetřit další fce. Schází mi nápady a možná i trochu systém.
Děkuji předem za rady.

edit: jedná se o fce přirozené proměnné, ale to vyjde stejně pro reálnou, že?

vanok · 09. 03. 2012 20:25

Ahoj ↑ Andrejka3:,
tvoja otazka ma suvis z asymptotickymy rebrikmy porovnania
"échelle de comparaison asymptotique"
A o tom je vela literatury... skus si to najst na google.

Andrejka3 · 09. 03. 2012 20:30

↑ vanok:
Děkuji, provedu.

vanok · 09. 03. 2012 21:16

↑ Andrejka3:,
jedna z najlepsie napisanych knih, co pise aj o tejto teme je Calcul infinitésimal:Jean Dieudonné .
Ak mozes, skus si ju aspon prelistovat.

Andrejka3

↑ vanok:
Bohužel, neumím francouzsky. Ale asi budou překlady - no ne, že bych nějaký na netu našla...
edit: je to tam. Našla, dík.

vanok · 09. 03. 2012 21:59

↑ Andrejka3:
aha, to si nasla po EN?

Mihulik · 10. 03. 2012 10:23

Ahoj,
doporučuji si to všechno přepsat na exponenciálu a je to z toho hezky vidět.
Dále pokud je nějaká fce malé o nějaké jiné, tak tím spíše je její velké O.

Andrejka3 · 10. 03. 2012 10:32

↑ Mihulik:
Tak například,
$(\ln \ln n)^{\ln n}= \exp (\ln n \ln \ln \ln n)$ a chci to porovnat s $(\ln n)^{\ln \ln n}= \exp \left( (\ln \ln n)^2\right)$ . Teď bych měla porovnat argumenty exp.
$\ln n \ln \ln \ln n$ s $\ln \ln n \ln \ln n$ . Co s tím?

Mihulik · 10. 03. 2012 10:52

No nejrychleji rostoucí člen je zde $ln\:n$ , který se vyskytuje pouze v jednom z výrazů. Navíc je ještě přenásoben něčím, co roste do nekonečna (sice pomalu, ale roste)... formálně z toho uděláš limitu a zjistíš, že $\lim_{n\to +\infty}\frac{(ln\:n)(lnlnln\:n)}{(lnln\:n)(lnln\:n)}=+\infty$

Andrejka3

↑ Mihulik:
A co mohu použít na výpočet té limity, prosím?
Tuším, že použití l'Hospitala přímo by asi nikam nevedlo. Napadá mě zkusit, jestli bude stačit ten nejrychlejší člen na ubití těch dvou ve jmenovateli:
$\lim_{n\to +\infty}\frac{(ln\:n)}{(lnln\:n)(lnln\:n)}=\lim_{n\to +\infty}\frac{1/n}{2(lnln\:n)1/(\ln\:n)1/n}=\lim_{n\to +\infty}\frac{\ln\:n}{2(lnln\:n)}=\infty$ .
Aha, děkuji, takže teď když vím, že jeden argument exponenciálny roste řádově rychleji než druhý, měla bych umět odůvodnit, proč i exponenciály dělají totéž. To bych asi zvládla přes nějaká okolí atd. Zkusím přijít na to, jak to udělat jinak...
Díky za rady.

Edit: ne, to stačí tak :)
Takže mám
$(\ln\:n)^{\ln\ln\:n}=o\left((\ln\ln\:n)^{\ln\:n}\right)$
A jestli se nepletu, tak
$\forall k \in \mathbb{N} : (\ln\ln\:n)^k=o(\ln\:n),\;\text{ pro }n \rightarrow \infty$
edit: proč mě ten poslední výsledek tak udivuje...

Mihulik

přesně tak:)
A zbytek už je analogický (tu tabulku jsem si taky udělal, takže ti pak když tak můžu pro kontrolu poslat, až to přepíšu...)... navíc se to dá snadno ověřit přes Wolfram;)

Andrejka3 · 10. 03. 2012 11:14

↑ Mihulik:
Hurá, dík. Ale bude mi to trvat. :P

Mihulik · 10. 03. 2012 11:17

Úplně nejjednodušší to budeš mít, když to vždycky ověříš přes Wolfram, že se nepleteš.:)

Andrejka3

Tabulka podle rychlosti růstu v nekonečnu. Fce, která je níže v tabulce je malé o funkce, která je výše (nahoře rostou rychleji).
$(\ln\:n)^{\ln\:n}$
$(\ln\ln\:n)^{\ln\:n}$
$n^2$
$ne^{\sqrt{\ln\:n}}$
$n \ln\:n$
$n2^{\ln\ln\:n}$
$n^{1+\frac{1}{\ln\:n}}$
$(\ln\:n)^{\ln\ln\:n}$

Limity
(1) $(\ln\:n)^{\ln\:n}$ , $(\ln\ln\:n)^{\ln\:n}$

Autor skryl část textu. Zobrazit/skrýt!

(2) $(\ln\ln\:n)^{\ln\:n}$ , $n^2$

Autor skryl část textu. Zobrazit/skrýt!

(3) $n^2$ , $ne^{\sqrt{\ln\:n}}$

Autor skryl část textu. Zobrazit/skrýt!

(4) $ne^{\sqrt{\ln\:n}}$ , $n\ln\:n$

Autor skryl část textu. Zobrazit/skrýt!

(5) $n \ln\:n$ , $n2^{\ln\ln\:n}$

Autor skryl část textu. Zobrazit/skrýt!

(6) $n2^{\ln\ln\:n}$ , $n^{1+\frac{1}{\ln\:n}}$

Autor skryl část textu. Zobrazit/skrýt!

(7) $n^{1+\frac{1}{\ln\:n}}$ , $(\ln\:n)^{\ln\ln\:n}$

Autor skryl část textu. Zobrazit/skrýt!

Edit: Vrátila jsem se k tomu o několik století později. Teď mě pořadí vyšlo takhle (a počítala jsem jiným způsobem, ale taky vše převedeno nejdříve na exp):
$(\ln n)^{\ln\ln n}\ll n^{1+\frac{1}{\ln n}}\ll n\ln n\ll n2^{\ln\ln n}\ll ne^{\sqrt{\ln n}}\ll n^{1+\frac{1}{\ln\ln n}}\ll n^2\ll (\ln\ln n)^{\ln n}\ll (\ln n)^{\ln n}$ .

Matematické Fórum

#1 09. 03. 2012 19:52 — Editoval Andrejka3 (09. 03. 2012 19:55)

Asymptotické chování, srovnání několika fcí

#2 09. 03. 2012 20:25

Re: Asymptotické chování, srovnání několika fcí

#3 09. 03. 2012 20:30

Re: Asymptotické chování, srovnání několika fcí

#4 09. 03. 2012 21:16

Re: Asymptotické chování, srovnání několika fcí

#5 09. 03. 2012 21:23 — Editoval Andrejka3 (09. 03. 2012 21:26)

Re: Asymptotické chování, srovnání několika fcí

#6 09. 03. 2012 21:59

Re: Asymptotické chování, srovnání několika fcí

#7 09. 03. 2012 22:41 Příspěvek uživatele Andrejka3 byl skryt uživatelem Andrejka3.

#8 10. 03. 2012 10:23

Re: Asymptotické chování, srovnání několika fcí

#9 10. 03. 2012 10:32

Re: Asymptotické chování, srovnání několika fcí

#10 10. 03. 2012 10:52

Re: Asymptotické chování, srovnání několika fcí

#11 10. 03. 2012 11:01 — Editoval Andrejka3 (10. 03. 2012 11:15)

Re: Asymptotické chování, srovnání několika fcí

#12 10. 03. 2012 11:11 — Editoval Mihulik (10. 03. 2012 11:14)

Re: Asymptotické chování, srovnání několika fcí

#13 10. 03. 2012 11:14

Re: Asymptotické chování, srovnání několika fcí

#14 10. 03. 2012 11:17

Re: Asymptotické chování, srovnání několika fcí

#15 11. 03. 2012 17:51 — Editoval Andrejka3 (23. 02. 2014 14:29)

Re: Asymptotické chování, srovnání několika fcí

Zápatí