Matematické Fórum

milwoukee

Ahoj , vie mi niekto poradit podla coho by som mal zoradovat casove zlozitosti resp. porovnat ich velkosti?

$a) 2^{n-8} b) (\sqrt{\sqrt{n}})^5 c) \log_{2}n^{12} d) \frac{(10^{n-2})}{(3^2*n) } e) \log_{10}n^n f) n^2 g) n$ ∗ $\log_{}n! h) n*\log_{10}n$

Dakujem za radu
Staci ked si podosadzam za n napriklad od 1 do 5 a porovnam?

za a) bude najpomalsi

mák · 31. 03. 2012 22:17

10000x opakovaní příslušného výpočtu trvalo v sekundách:

a - 0.54
b - 2.54
c - 1.64
d - 0.70
e - 0.76
f - 0.37
g - 0.65
h - 1.03

Zajímavá je možnost b) která vyšla nejpomalejší, což jsem vůbec nepředpokládal

pizet · 31. 03. 2012 22:25 — Editoval pizet (31. 03. 2012 22:40)

↑ mák:

Ahoj.

Celkom mi nie je jasné, že čo si ty počítal.

pizet · 31. 03. 2012 22:31 — Editoval pizet (31. 03. 2012 22:39)

↑ milwoukee:

Ahoj.

milwoukee napsal(a):
Staci ked si podosadzam za n napriklad od 1 do 5 a porovnam?

To určite nestačí. Nejaká funkcia môže mať pre malé n menšie hodnoty ako druhá ale pre n idúce do nekonečna môže byť situácia úpne iná.

Príklad. Uvážme funkcie

$f(n) = 10n+40$ a $g(n) = n^2$ .

Je vidieť, že pre malé n vracia funkcia f väčšie hodnoty ako funkcia g. Avšak to už neplatí pre

$n\geq 14$ .

Teda tu by tvoj postup určite neuspel.

Z kade máš túto úlohu? Máš k tomu aj nejaké teoretické znalosti? Je ti napríklad známa notácia "veľké Ó"?

milwoukee

↑ pizet:
Ahoj mam viac menej nejake teoreticke znalosti. Ak myslis omikron tak f patri O(g) znamena ze f rastie nanajvys tak rychlo ako g.
To s tym dosadzanim som si aj myslel ze nepojde tak , ale potom ma nenapada ako riesit tento typ prikladov...
Jedine zeby delenim limit tych rychlosti, ale neda sa to aj nejak rychlejsie?

pizet · 31. 03. 2012 22:42 — Editoval pizet (31. 03. 2012 22:42)

↑ milwoukee:

No môžeš si napríklad typnúť, že ktorá funkcia bude pre veľké n nadobúdať väčšie hodnoty a potom sa to pokúsiť formálne dokázať.

milwoukee

↑ mák:

Ahoj , nemyslel som ako rychlo pocita tieto priklady pocitac ale porovnat rychlost rastu tychto funkcii...

milwoukee

↑ pizet:
Pri tom ma napada len ze pre $N>1$ plati, ze $n < n*n$ ale neviem ako pri tych zlozitejsich...

Pri tomto pripade je to zjavne ze sa to meni na 1notke a potom nas to uz neprekvapi...

pizet · 31. 03. 2012 22:53

Napríklad môžeš porovnať rýchlosť rastu funkcií

$n$ a $n^2$

tak, že uvážiš, že

$\lim_{n\rightarrow\infty}\frac{n}{n^2} = 0$ ,

teda $n = o(n^2)$ .

Záver je, že funkcia $n$ rastie postatne pomalšie než funkcia $n^2$ .

Jookyn · 31. 03. 2012 23:02

Obecne se to resi vetsinou tak, ze se funkce prevedou do exponencialni funkce tvaru $e^{x}$ a pak se porovnavaji ty ruzne fce x, pujde to jednoduseji, vetsinou to bude jen nejaka konstanta krat linearni/kvadraticka fce...

Pro faktorial bude potreba prvne pouzit nejaky rozumny odhad (treba Stirlinguv vzorec)...

Jinak na prvni pohled bych rekl, ze nejrychleji rostouci bude d) a nejpomaleji c)...

milwoukee · 31. 03. 2012 23:15

↑ Jookyn:
Aha dik,a ako by som mal previest napr. moznost B?

pizet · 01. 04. 2012 01:22 — Editoval pizet (01. 04. 2012 01:26)

↑ milwoukee:

$\left(\sqrt{\sqrt{n}}\right)^5 = e^{\frac{5}{4}\log{n}}$

Použíl som definíciu všeobecnej mocniny :

Nech $a>0$ a $b\in\mathbb{R}$ , potom definujeme $a^b = e^{b\log{a}}$ .

milwoukee

↑ pizet:
Dik , este by som sa rad spytal ako napr. $\log_{2}n^{12}$ pretavim na ten tvar $e^x$ , je nejaky vzorec na to?

Aha to podla toho isteho vzorca v zmysle $12* \log_{2}n = e^{\log_{10}(log_{2}n)}$ ??
A mozme pri logaritmoch zanedbavat zaklady v takychto pripadoch?

pizet · 01. 04. 2012 16:15

↑ milwoukee:

milwoukee napsal(a):
Dik , este by som sa rad spytal ako napr. $\log_{2}n^{12}$ pretavim na ten tvar $e^x$ , je nejaky vzorec na to?

Aha to podla toho isteho vzorca v zmysle $12* \log_{2}n = e^{\log_{10}(log_{2}n)}$ ??

Správne, i keď tie logaritmy, ktoré som písal v tej definícii sú prirodzené.

milwoukee napsal(a):
A mozme pri logaritmoch zanedbavat zaklady v takychto pripadoch?

No môžeme. Je známa nasledujúca definícia:

Ak sú $a, b>0$ , tak definujeme $\log_b{a}=\frac{\log{a}}{\log{b}}$ .

Z toho plynie, že logaritnus o ľubovoľnom základe je len konštanta krát logaritmu o základe e a konštanty pri určovaní asymptotickej časovej zložitosti zanedbávame. Väčšinou sa píše proste $\log{n}$ .

Pozor! Napríklad pri funkcii $n^{\log_2{3}}$ naopak veľmi záleží na tom, aký má logaritmus v exponente základ.

Matematické Fórum

#1 31. 03. 2012 18:21 — Editoval milwoukee (31. 03. 2012 18:34)

Zoradenie fci casovych zlozitosti

#2 31. 03. 2012 22:17

Re: Zoradenie fci casovych zlozitosti

#3 31. 03. 2012 22:25 — Editoval pizet (31. 03. 2012 22:40)

Re: Zoradenie fci casovych zlozitosti

#4 31. 03. 2012 22:31 — Editoval pizet (31. 03. 2012 22:39)

Re: Zoradenie fci casovych zlozitosti

milwoukee napsal(a):

#5 31. 03. 2012 22:39 — Editoval milwoukee (31. 03. 2012 22:41)

Re: Zoradenie fci casovych zlozitosti

#6 31. 03. 2012 22:42 — Editoval pizet (31. 03. 2012 22:42)

Re: Zoradenie fci casovych zlozitosti

#7 31. 03. 2012 22:42 — Editoval milwoukee (31. 03. 2012 22:52)

Re: Zoradenie fci casovych zlozitosti

#8 31. 03. 2012 22:46 Příspěvek uživatele pizet byl skryt uživatelem pizet. Důvod: Hlúposť

#9 31. 03. 2012 22:50 — Editoval milwoukee (31. 03. 2012 22:52)

Re: Zoradenie fci casovych zlozitosti

#10 31. 03. 2012 22:53

Re: Zoradenie fci casovych zlozitosti

#11 31. 03. 2012 23:02

Re: Zoradenie fci casovych zlozitosti

#12 31. 03. 2012 23:15

Re: Zoradenie fci casovych zlozitosti

#13 01. 04. 2012 01:22 — Editoval pizet (01. 04. 2012 01:26)

Re: Zoradenie fci casovych zlozitosti

#14 01. 04. 2012 14:47 — Editoval milwoukee (01. 04. 2012 15:31)

Re: Zoradenie fci casovych zlozitosti

#15 01. 04. 2012 16:15

Re: Zoradenie fci casovych zlozitosti

milwoukee napsal(a):

milwoukee napsal(a):

Zápatí