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
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
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: 759
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