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

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

#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ů.

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

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.

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.