Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
🔒 23. 3. 2019 Přešli jsme na HTTPS. Prosíme o kontrolu funkčnosti fóra.
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

milwoukee
Příspěvky: 158
Reputace:   
 

Zoradenie fci casovych zlozitosti

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

Offline

 

#2 31. 03. 2012 22:17

mák
Místo: Vesmír, Galaxie MD
Příspěvky: 739
Reputace:   57 
 

Re: Zoradenie fci casovych zlozitosti

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

Offline

 

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

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

↑ mák:

Ahoj.

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


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

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

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

↑ 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é Ó"?


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

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

milwoukee
Příspěvky: 158
Reputace:   
 

Re: Zoradenie fci casovych zlozitosti

↑ 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?

Offline

 

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

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

↑ 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ť.


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

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

milwoukee
Příspěvky: 158
Reputace:   
 

Re: Zoradenie fci casovych zlozitosti

↑ mák:

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

Offline

 

#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)

milwoukee
Příspěvky: 158
Reputace:   
 

Re: Zoradenie fci casovych zlozitosti

↑ 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...

Offline

 

#10 31. 03. 2012 22:53

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

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$.


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

#11 31. 03. 2012 23:02

Jookyn
Místo: Mar. Lázně / Praha
Příspěvky: 143
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

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)...

Offline

 

#12 31. 03. 2012 23:15

milwoukee
Příspěvky: 158
Reputace:   
 

Re: Zoradenie fci casovych zlozitosti

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

Offline

 

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

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

↑ 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}}$.


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

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

milwoukee
Příspěvky: 158
Reputace:   
 

Re: Zoradenie fci casovych zlozitosti

↑ 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?

Offline

 

#15 01. 04. 2012 16:15

pizet
Místo: Levice/Praha
Příspěvky: 459
Reputace:   11 
 

Re: Zoradenie fci casovych zlozitosti

↑ 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.


Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson