Algoritmus - priklad – Offtopic – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Algoritmus - priklad – Offtopic – Fórum – Programujte.comAlgoritmus - priklad – Offtopic – Fórum – Programujte.com

 

Booty
~ Anonymní uživatel
3 příspěvky
7. 9. 2015   #1
-
0
-

Zdravim ,momentalne sa zaoberam algoritmami a citam jednu knizku,v ktorej je zlozitost  

(n^2)/4+6n+12

a mna by zaujimalo ,ako moze takyto algoritmus vyzerat,pretoze vzdy som videl len n^2 alebo n a podobne.
Jednoducho povedane tie cisla co znamenaju,to n^2 beriem ako vnoreny cyklus,6n by som pochopil ako 6x for a tu 12ku ako pocet nejakych jednoduchych operacii ,spocitanie priradenie a podobne.Ale tu 4 som tam vobec nepochopil,ak sa niekde mylim kludne ma opravte ,dakujem vopred :)

Nahlásit jako SPAM
IP: 78.98.15.–
ondrej39+1
Věrný člen
7. 9. 2015   #2
-
0
-

#1 Booty
Jestli to není náhodou ((n^2)/4)+6n+12, tj. v nejhorším případě se v tom vnořeném cyklu projede maximálně čtvrtina kvadrátu počtu prvků.

Nahlásit jako SPAM
IP: 79.141.243.–
Inject all the dependencies!
peter
~ Anonymní uživatel
4014 příspěvků
8. 9. 2015   #3
-
0
-

kdyz n*n je dvojity cyklus, tak 1/4 je 1/4 toho cyklu. Predstavil bych si to jako
n = 16
n4 = n / 4
cyklus (i<n4) (j<n4) nebo
cyklus (i<n) (j<n4) nebo

Treba, kdyz delas serazovani prvku, tak nejrychlejsi algoritmy pracuji tak, ze rozdeli celou skupinu na nekolik podskupin. ty seradi. a pak seradi celek. A protoze podskupiny jsou jiz serazene, tak nemusi porovnavat vsechny prvky ze dvou podskupin.
6 5 4 3 2 1
4 5 6 | 1 2 3
4<1 - 1 a 4 jsou nejmensi ve skupine; 1 je mensi; neni treba porovnavat znovu 1 2 a 1 3 ani nove 1 5 a 1 6
Je to, jak si to myslim, takze mozna je skutecnost uplne jina, slozitosti neresim :)

Nahlásit jako SPAM
IP: 193.84.207.–
Booty
~ Anonymní uživatel
3 příspěvky
8. 9. 2015   #4
-
0
-

Aha:-))) mohli by ste mi este trošku vysvetliť ako sa ráta pamäťova zlozitost? Nejaky príklad najlepšie Ďakujem veľmi pekne :)

Zasláno z mobilního telefonu.

Nahlásit jako SPAM
IP: 78.98.15.–
peter
~ Anonymní uživatel
4014 příspěvků
9. 9. 2015   #5
-
0
-

Podle algoritmu. Bud pamet potrebuje nebo ne. Nevim, jestli se to nejak matematicky pocita, opet neresim :)
Jako, kdyz si napises program, ze vola sebe sama, tak si brzo vyplacas pamet a vykon cpu pri vetsim poctu prvku na dnesnich pc.
serad(a,b) {... serad(a,b); ... }

Bubble sort - tmp = a; a<b ? a=b b=tmp - to potrebuje 1 bunku v pameti pro tmp + pamet, kde ma ulozene cele pole, ktere chces seradit

Sito - rozdelujes prvky na vetsi nez x a mensi nez x. Tak je dobre mit pamet, kde mas cele pole + 2 x pamet, kam ukladas vetsi ci mensi. Pripadne staci 1x pamet, kdyz ukladas mensi na zacatek a vetsi na konec.
Netusim, jak by se tohle dalo pocitat obecne :)

Insert sort - Najde nejmensi hodnotu a vymeni ji z prvni polozkou. To mas jam bubble, s pameti. Tez mu staci mit nekde cele pole a 1-2 bunky navic.

Slevani (tusim je to upravene Merge sort) - najdes serazene skupiny  a ty postupne slevas dohromady podle nejmensich prvku (viz minula zprava). Je samozrejme lepsi delat to pres pomocne pole, ale asi to jde napsat i usporne.
 

Nahlásit jako SPAM
IP: 193.84.207.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 10 hostů

Podobná vlákna

Příklad — založil uzi

Příklad — založil Hana

Příklad — založil Ovladač

Příklad — založil uzi

Priklad — založil ukulele

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý