Matematické Fórum

aGr · 15. 11. 2011 10:32

Zdravím, potřeboval bych poradit s tímto přikladem.

Doplňte místo otazníku symbol, aby platil vztah $\frac{\log{n}}{n} = ?(\frac{1}{\sqrt{n}})$ :
a) o
b) O (a současně nelze použít ani o ani Θ)
c) Θ
d) Ω (a současně nelze použít ani Θ ani ω)
e) ω

Asi by to chtělo určit asymptotickou složitost jendotlivých funkcí? To bych řekl, že je $O(log n\cdot n)$ u prvního a u druhého $O(n)$ . To však nejspíš ale bude špatně neboť správná odpověď je za a).

Díky moc za jakoukoliv radu.

Rumburak · 15. 11. 2011 10:42

↑ aGr:
Zdravím též.
Podívej se na definice těch asymptotických relací a zjisti, kterým z nich ty funkce $\frac{\log{n}}{n}, \frac{1}{\sqrt{n}}$ vyhovují.

aGr · 15. 11. 2011 11:42

↑ Rumburak:

Díky, řekněme, že bych tedy začal $O$ . Musí tedy platit, že:

$\exists c\in R^{+}, \exists n_0 \in N, \forall n\ge n_0:$
$\frac{\log{n}}{n}\le c \frac{1}{\sqrt{n}}$

Nyní by asi bylo příhodné nerovnici upravit. Po umocnění dostávám:
$\log^{2}{n} \cdot \frac{1}{n} \le c^2$

Nyní je, předpokládám, důležité ukázát, že zde nemůže nastat rovnost (abych mohl $O$ vyloučit). Tedy po úpravě:
$\frac{\log{n}}{\sqrt{n}} = |c|$

Jak z toho však můžu vyvodit, že takové c neexistuje? Doufám, že mé úpravy jsou správé.

Rumburak · 15. 11. 2011 14:11

↑ aGr:

Přecházet k rovnosti $\frac{\log{n}}{\sqrt{n}} = |c|$ byla chyba.

Z nerovnosti $\frac{\log{n}}{n}\le c \frac{1}{\sqrt{n}}$ snadno dostaneme její ekvivalentní tvar

(1) $\frac{\log{n}}{\sqrt{n}}\le c$

a máme rozhodnout, zda existuje c > 0 takové, aby (1) byla splněna pro každé dostatečně velké n.

U tohoto druhu úloh nám může pomoci spočítat limitu levé strany v (1) pro $n \to \infty$ , pokud existuje.
Co dostaneme ?

Měco o tom najdeš také zde.

aGr · 15. 11. 2011 14:45

Limita je rovna 0. Tu 0 to ale reálně nikdy nedosáhne, že? Tudíž vždy mohu najít takové c, které je větší než 0. Až v onom nekonečnu by to nešlo.

Rumburak · 15. 11. 2011 15:15

↑ aGr:
Ano, ta limita (označme ji L) je 0, takže když ve standardně vyslovené definici limity budeme psát $c$ místo $\varepsilon$ , odvodíme z ní výrok

" ke každému c > 0 existuje D takové, že pro všechna n > D je $\frac{\log{n}}{\sqrt{n}}\le c$ " ;

když ke každému c > 0, tak například i k c = 5 , takže

" existuje D takové, že pro všechna n > D je $\frac{\log{n}}{\sqrt{n}}\le 5$ " ,

neboli ekvivelentně

" existuje D takové, že pro všechna n > D je $\frac{\log{n}}{n}\le 5 \cdot \frac{1}{\sqrt{n}}$ " .

Kladné číslo c požadované definicí výroku

(1) $\frac{\log{n}}{n} = O(\frac{1}{\sqrt{n}})$

jsme tedy našli (a sice číslo 5, ale mohli jsme vzít i jiné vhodné), takže platnost výroku (1) je tím dokázána .

Podobným postupem - jen o málo složitějším - bychom došli k témuž výsledku, pokud by ta limita L byla kladná a konečná.

ALE: speciální případ L = 0 znamená více než (1). Projdi si ještě jednou pořádně všechny ty definice a najdi tu ptřičnou
(ale v tom odkaze, co jsem minule poslal, ta patřičná bohužel chybí).