Matematické Fórum

Schnappi · 17. 11. 2015 18:52

Dobrý deň,
snáď niekoho napadne nejaký hint:

Majme funkciu $g(n): \mathbb{N} \rightarrow \mathbb{R^{+}}$ a dve množiny definované takto:
$o(g(n)) = \{ f(n):\mathbb{N} \rightarrow \mathbb{R^{+}} | (\forall c\in \mathbb{R^{+}}) ( \exists n_{0}\in \mathbb{N}) (\forall n\ge n_{0}): f(n)<c\cdot g(n) \}$
$\bar{o}(g(n)) = \{ f(n):\mathbb{N} \rightarrow \mathbb{R^{+}} | (\forall c\in \mathbb{R^{+}}) ( \exists n_{0}\in \mathbb{N}) (\forall n\ge n_{0}): f(n)\le c\cdot g(n) \}$
Dokážte, že obe množiny sú totožné a vyvoďte z toho dôsledok pre definíciu $o$ .

Dokazujem, že množiny sa rovnajú, teda ma napadlo, že dokážem dve množinové inklúzie. Jedna z nich je triviálna. Dokázať druhú je už ťažšie.Nejaké rady? Ďakujem.

Stýv · 17. 11. 2015 19:13

hint: z neostré nerovnosti pro $\frac c2$ plyne ostrá nerovnost pro $c$

Schnappi · 20. 11. 2015 03:02

super, ďakujem! :)

Matematické Fórum

#1 17. 11. 2015 18:52

Množiny, zložitosť algoritmov

#2 17. 11. 2015 19:13

Re: Množiny, zložitosť algoritmov

#3 20. 11. 2015 03:02

Re: Množiny, zložitosť algoritmov

#4 24. 11. 2015 23:24 Příspěvek uživatele Schnappi byl skryt uživatelem Schnappi.

Zápatí