Matematické Fórum

Frantik88 · 05. 10. 2010 00:01

Ahoj, mám problém, se kterým si nevím rady.

"Ukažte, že (log n)^2 = O(n^b)"

Dekuji za pomoc.

Oxyd · 05. 10. 2010 00:24

Jak máš zadefinované velké O? Já znám takovouhle definici: $\log^2 n \in O \left( n^b \right) \Leftrightarrow (\exists c > 0)(\exists n_0)(\forall n \ge n_0) \left( \log^2 n \le cn^b \right)$

Pokud máme stejné definice, tak je to jenom záležitost nalezení takových c a b, aby nerovnost $\log^2 n \le cn^b$ platila pro skoro všechna n.

Můžeš to například jako nerovnici odmocnit (od jedničky dál je log n stejně nezáporný) a potom "odlogaritmovat". Z toho už by mělo jít vidět, jak se dají c, b určit.

Frantik88 · 05. 10. 2010 00:33

Ano, presne takto mam zadefinovane O.

Jenom jsem tam udelal malou (velkou chybu v zadani). Melo to byt takto: "Ukažte, že (log n)^a = O(n^b)".

Frantik88 · 05. 10. 2010 00:36

Kdybych to cele zlogaritmoval, dostal bych: log( (log n)^a ) <= log k + b * log n

Nevim si pak ale rady s tou levou stranou. :(

Oxyd · 05. 10. 2010 00:47

↑ Frantik88:

Ne zlogaritmoval, ale odlogaritmoval -- tzn. hodil to do exponentu e nebo 10 nebo 2 nebo co je základ toho logaritmu.

Ta a, b v exponentech mám chápat jak? Má to platit pro všechna (kladná, přirozená) a, b? Nebo máme ke každému a najít b? Nebo máme najít nějaká taková a, b, aby to platilo?

Frantik88 · 05. 10. 2010 00:49

Ukažte, že (log n)^a = O(n^b) pro b > 0. tot vse

Pavel · 05. 10. 2010 11:50 — Editoval Pavel (05. 10. 2010 11:51)

↑ Oxyd:

nerovnost $\log^2 n \le cn^b$ má platit pro dostatečně velká n, ne pro skoro všechna n. V tom je velký rozdíl.

↑ Frantik88:

Stačí vyjít z faktu, že

$\lim_{n\to\infty}\frac{\log^2n}{n^b}=0,\qquad\text{pro }b>0.$

Matematické Fórum

#1 05. 10. 2010 00:01

Důkaz asymptotické složitosti

#2 05. 10. 2010 00:24

Re: Důkaz asymptotické složitosti

#3 05. 10. 2010 00:33

Re: Důkaz asymptotické složitosti

#4 05. 10. 2010 00:36

Re: Důkaz asymptotické složitosti

#5 05. 10. 2010 00:47

Re: Důkaz asymptotické složitosti

#6 05. 10. 2010 00:49

Re: Důkaz asymptotické složitosti

#7 05. 10. 2010 11:50 — Editoval Pavel (05. 10. 2010 11:51)

Re: Důkaz asymptotické složitosti

Zápatí