Matematické Fórum

Mr.PropperD · 01. 11. 2014 15:33

Ahoj,

potřeboval bych pomoci s následujícími třemi příklady (dokázat / vyvrátit), nevím, jak přesně se na to podívat.

1) $log n^{n} = O ( n^{log ( n ) } )$
Zde jsem nějakým způsobem došel k místu, kde jsem si řekl, že $n^{2}$ zdola omezuje $n^{log(n)}$ , tím pádem $log (n^{n})$ je shora omezeno $n^{2}$ , protože to mohu zapsat jako $n * log (n)$ , o čemž "víme", že je pravda.
Otázka zní, jestli jsou mé úvahy správné, případně jak tomu dát nějakou elegantní formu. Podle Mathematicy se grafy jeví podle mé představy.

2) 2 nezáporné fce f, g. Pokud $f(n) = \sigma (g(n))$ , potom také $2^{f(n)} = O (2^{g(n)}$ .
Zde si myslím, že by to mělo platit, neplatilo by to v případě, že by $f(n) = O (g(n))$ , ovšem také vůbec nevím, jak to ukázat.

3) 3 nezáporné fce f, g, h: Pokud $f(n) = \Theta (g(n))$ a $g(n) = \Theta (h(n))$ , potom také $f(n) = \Theta (h(n))$ .
To se mi jeví jako zřejmé, ale bohužel opět nevím, jak to ukázat.

Předpokládám, že 2) a 3) by mělo jít nějak "jednoduše" z definice.

Mockrát díky.

OndrasV · 12. 11. 2014 16:05

1) říká, že existuje konečná limita $lim_{n \to \infty} \frac{\ln (n^{n})}{n^{\ln( n)}}=K, |K|\le k$ .

Brano · 12. 11. 2014 16:24

1) najpr prosim dopln ci sa tym mysli $(\log n)^n$ alebo $\log(n^n)$ lebo to je rozdiel
2) prosim napis co je $\sigma$ nie je to az tak bezne
3) ta je naozaj priamo z definicie

$a\cdot g(n)\le f(n)\le b\cdot g(n)$ a $c\cdot h(n)\le g(n)\le d\cdot h(n)$ implikuje $ac\cdot h(n)\le f(n)\le bd\cdot h(n)$

Matematické Fórum

#1 01. 11. 2014 15:33

Důkaz / vyvrácení tvrzení asymptotické složitosti

#2 12. 11. 2014 16:05

Re: Důkaz / vyvrácení tvrzení asymptotické složitosti

#3 12. 11. 2014 16:24

Re: Důkaz / vyvrácení tvrzení asymptotické složitosti

Zápatí