Matematické Fórum

nordec · 18. 03. 2010 15:12

Prosím, poradí někdo, zda je $ln(x)=\mathcal{O}(log_2(x^2))$ nebo $ln(x)=\Theta(log_2(x^2))$ ?

Limita mi vyšla $\lim_{x\to\infty}\frac{log_2(x^2)}{ln(x)}=\lim_{x\to\infty}\frac{2}{ln(2)}=2,9$ .

Díky.

Olin · 18. 03. 2010 15:48 — Editoval Olin (18. 03. 2010 15:48)

Platí obě "rovnosti" - z $f = \Theta(g)$ už podle definice plyne i $f = \mathcal{O}(g)$ .

nordec · 18. 03. 2010 16:08

Takže neplatí $f(x)=\Theta(g(x))$ když $\lim_{x\to\infty}\frac{g(x)}{f(x)}=1$ ?

Olin · 18. 03. 2010 16:14

Pokud je mi známo, tak $f = \Theta(g)$ znamená, že existují taková $A,\, B,\, x_0 \in \mathbb{R}^+$ , že $A\cdot |g(x)| \leq |f(x)| \leq B\cdot |g(x)|$ pro $x \geq x_0$ . To nastane speciálně tehdy, když $$\lim_{x \to \infty}\frac{f(x)}{g(x)}$ \in \mathbb{R} \setminus \{0\}$ .

nordec · 18. 03. 2010 16:49

Mám v tom značení zmatek. Platí

$f(x)=\mathcal{O}(g(x))$ když $\lim_{x\to\infty}\frac{f(x)}{g(x)}<\infty$
$f(x)=\Omega(g(x))$ když $\lim_{x\to\infty}\frac{g(x)}{f(x)}<\infty$
$f(x)=\mathcal{o}(g(x))$ když $\lim_{x\to\infty}\frac{f(x)}{g(x)}=0$
$f(x)=\omega(g(x))$ když $\lim_{x\to\infty}\frac{g(x)}{f(x)}=0$ ?

Pokud ano, pak by opravdu obě rovnosti platily, protože $\Theta$ to má s limitou podobně jako $\mathcal{O}$ . Je mezi těmi dvěma nějaký rozdíl nebo je jedno, který z nich použít?

Jakým symbolem se zapíše když $\lim_{x\to\infty}\frac{g(x)}{f(x)}=1$ ?

Olin · 18. 03. 2010 19:14

Doporučuji se podívat na definice jednotlivých značek. Jinak všechny výroky, které jsi uvedl, jsou skoro pravdivé (ve smyslu $\lim_{x\to\infty}\frac{f(x)}{g(x)}<\infty \, \Rightarrow \,f(x)=\mathcal{O}(g(x))$ atd., ne naopak), ještě by se musel ošetřit extrémní záporný případ ( $\lim = -\infty$ ). Nevím přesně, co myslíš tím, že "je jedno, který použít" - opravdu obě "rovnosti" (píšu v uvozovkách, jelikož nejde o skutečné rovnosti) platí, ovšem ta s $\Theta$ nám poskytuje více informací.

nordec · 18. 03. 2010 19:46 — Editoval nordec (18. 03. 2010 19:58)

Z odkazu už vím, jak je to s limitou rovno jedné, díky.

Když obě "rovnosti" platí (ani limita je nerozliší), nepoznám který z těch dvou symbolů je správnější. Tím "je jedno, který použít" myslím, že ať použiju $\Theta$ nebo $\mathcal{O}$ , nebude to nějakým šťouralem bráno jako chyba?

nordec · 19. 03. 2010 13:10

Znamená to, že jakákoli funkce, která je $\mathcal{O}(g)$ , je také $\Theta(g)$ a naopak?

Pavel · 19. 03. 2010 13:22 — Editoval Pavel (19. 03. 2010 13:23)

↑ nordec:

To ne. Je-li $f=\Theta(g)$ , pak samozřejmě také $f=\mathcal{O}(g)$ . Naopak to neplatí. Stačí vzít funkce $f(x)=\ln x$ a $g(x)=x$ . Pak $\ln x=\mathcal{O}(x)$ avšak $\ln x\neq\Theta(x)$ . Kdyby existovala kladná konstanta $c$ taková, že $cx<\ln x$ , muselo by pak platit $c<\frac{\ln x}x$ . Avšak $\lim_{x\to\infty}\frac{\ln x}x=0$ . Takže takové kladné $c$ existovat nemůže.

nordec · 19. 03. 2010 13:41 — Editoval nordec (19. 03. 2010 13:43)

Takže když platí $ln(x)=\Theta(log_2(x^2))$ i $ln(x)=\mathcal{O}(log_2(x^2))$ , je lepší napsat to první, protože je to přesnější.

Pavel · 19. 03. 2010 14:14 — Editoval Pavel (19. 03. 2010 14:15)

↑ nordec:

Jo. Přesně tak. Tím prvním říkáš, že znáš horní i dolní odhad. Tím druhým říkáš, že znáš jen horní odhad. Pokud Ti ale v konkrétní situaci stačí znát jen horní odhad, použil bych ten druhý zápis. Je známější.

nordec · 19. 03. 2010 15:01

Super. Už je mi to značení jasnější. Moc díky za pomoc;)

Matematické Fórum

#1 18. 03. 2010 15:12

Rychlost růstu funkcí

#2 18. 03. 2010 15:48 — Editoval Olin (18. 03. 2010 15:48)

Re: Rychlost růstu funkcí

#3 18. 03. 2010 16:08

Re: Rychlost růstu funkcí

#4 18. 03. 2010 16:14

Re: Rychlost růstu funkcí

#5 18. 03. 2010 16:49

Re: Rychlost růstu funkcí

#6 18. 03. 2010 19:14

Re: Rychlost růstu funkcí

#7 18. 03. 2010 19:46 — Editoval nordec (18. 03. 2010 19:58)

Re: Rychlost růstu funkcí

#8 19. 03. 2010 13:10

Re: Rychlost růstu funkcí

#9 19. 03. 2010 13:22 — Editoval Pavel (19. 03. 2010 13:23)

Re: Rychlost růstu funkcí

#10 19. 03. 2010 13:41 — Editoval nordec (19. 03. 2010 13:43)

Re: Rychlost růstu funkcí

#11 19. 03. 2010 14:14 — Editoval Pavel (19. 03. 2010 14:15)

Re: Rychlost růstu funkcí

#12 19. 03. 2010 15:01

Re: Rychlost růstu funkcí

Zápatí