Matematické Fórum

VojtechSejkora

Potřeboval bych poradit s jedním mím programem, který mám na KSP je to doprovodný program k algoritmu, ale nejsem si jist, jestli jsem odhadl správně jeho časovou složitost.... příjde mi až moc pěkná:)

Code:

for(int k=1;k<=(maxHodnota-minHodnota)/2;k++){
            for(i=0;i<k;i++){
                Prepravka p = null;
                najdiPrvniTrojici(i, k);

                for(int j=indexTreti;j<jednotlivePrvky.length-2; ){   
                    if((p=binarniHledani(j, prvni+2*k, prvni+2*k)).je){
                        System.out.print(prvni+"->");
                        prvni=druhy;
                        druhy=jednotlivePrvky[p.index];
                        System.out.print((prvni)+"->"+(druhy)+ " , ");
                       j=p.index;
                    }else{
                        najdiPrvniTrojici(j, k);
                        j=indexTreti;
                    }
                }}}/*konce cyklů*/

a ještě aby jste viděli tu najdiPrvniTrojici(int,int)

Code:

static void najdiPrvniTrojici(int from,int k){        
    if(from<jednotlivePrvky.length){
        prvni=jednotlivePrvky[from];
        Prepravka p;
        
            if((p=binarniHledani(prvni,prvni+k,prvni+k)).je){
                druhy=jednotlivePrvky[p.index];
                if((p=binarniHledani(p.index, prvni+2*k, prvni+2*k)).je){
                    System.out.print(prvni+"->");
                    prvni=druhy;
                    druhy=jednotlivePrvky[p.index];
                    System.out.print((prvni)+"->"+(druhy)+ " , ");
                    indexTreti=p.index;
                }else
                    indexTreti=jednotlivePrvky.length;
            }else
                indexTreti=jednotlivePrvky.length;
        }else
                indexTreti=jednotlivePrvky.length;
    }

omlouvám se, ale zobecnit to neumím, můj odhad časové složitosti je O(N), ale nejsem si tím jist....

vojta01 · 27. 11. 2010 16:28

Ahoj, bylo by dobré kód okomentovat, ale pokusím se ti poradit.
Program je tuším v Javě, já umím C++. Předpokládám, že "jednotlivePrvky" je pole o počtu N prvků.
Časová složitost funkce "najdiPrvniTrojici" je závislá na časové složitosti funkce "binarniHledani". Bylo by dobré napsat i tuto funkci nebo alespoň její složitost, já si její složitost označím jako B => časová složitost funkce "najdiPrvniTrojici" je O(B).

Za předpokladu, že v 1. kódu je hodnota "maxHodnota-minHodnota" konstantní (pole má N prvků s čísly v rozsahu od 1 do MAX_INT), pak cykly for(int k=1... a for(i=0... budou mít konstatní časovou složitost v nejhorším případě (pořád stejnou časovou složitost v nejhorším případě). Cyklus "for(int j=indexTreti..." samotný má časovou složitost O(N), v něm se provede funkce "binarniHledani" nebo "najdiPrvniTrojici", které mají obě časovou složitost O(B), čili časová složitost prvního programu bude O(N*B), kde N je počet prvků pole "jednotlivePrvky" a O(B) je časová složitost funkce "binarniHledani".

Pokud tomu nerozumíš, ozvi se.

VojtechSejkora · 27. 11. 2010 18:50

↑ vojta01:
tak tomu rozumím

vzhledem k tomu že jsem tu metodu nazval binární hledání, tak jsem předpokládal že bude jasné, že hledá binárně tedy nějakej log N/2 maximálně.... to až pro to nejvyšší k....

takže to binární hledání je log k
přičemž to s tím k se provede maxilmálně N krát (pak sjem si všiml chybi a toto opravil u sebe, bohužel tu již ne)

takže celková složitos je pak O(N * log N)? a nebo se to logaritmické hledání nebude počítat?

a za to že jsme neudělal komentáže se omlouvám, ale nemám ve zvyku psát do komentářů něco jiného než co to vlastně dělá.... a to pro určení časové složitosti snad není důležité ne? co to dělá, ale jsou tam důležité ty cykli

tak díky ještě mi tedy řekni když už víš to binární hledání jak funguje jestli to je N log N a nebo něco jiného
dík

pizet · 27. 11. 2010 22:44 — Editoval pizet (27. 11. 2010 22:46)

VojtechSejkora napsal(a):
...
takže celková složitos je pak O(N * log N)? a nebo se to logaritmické hledání nebude počítat?

a za to že jsme neudělal komentáže se omlouvám, ale nemám ve zvyku psát do komentářů něco jiného než co to vlastně dělá.... a to pro určení časové složitosti snad není důležité ne? co to dělá, ale jsou tam důležité ty cykli
...

Ak máš N*logN tak to musíš zarátať, nemusel by si, keby si mal dajme tomu N + logN

A ja som sa raz stretol so zdrojovým kódom (konkrétne v knihe Algoritmy a programovacie techniky od pána Töpfera) k programu prehľadávanie grafu do hĺbky, čo ako všetci vieme, že má časovú zložitosť $O(N+M)$ , prípadne $O(N^2)$ (N - počet vrcholov, M - počet hrán) a boli v ňom 3 do seba vnorené cykly, čo mohlo budiť dojem, že bude $O(N^3)$ (čo samozrejme nie je zle ale zbytočne nepresné) a autor sám na túto vec poukazuje, čiže imho to čo to vlastne robí je veľmi dôležité a nie sú to len tie cykly čo sú pre určenie časovej zložitosti dôležité.

VojtechSejkora

↑ pizet:
a k tomu N*log N vs. N+logN...vím že se vždy započítává jen ta nejvyšší, tedy kdybych měl N^2+N*log N tak stále to bude $O(N^2)$

no tak co to dělá....
pro jednotlivé k, která můžou být maximálně mensí z N a (maximálníHodnota-minimálníHodnota)/2
projde celou řadu, přičemž si pamatuje předchozí 2 prvky a najde zbylý jeden....ten prvek hledá logaritmicky ve vzdálenosti toho 2.prvku + k tedy ne celé pole
pokud takový nenajde, tak hledá od začáku první 3 a až pak vypisuje.... a takto to udělá pro všechna k....

tak asi tak to funguje a já tipuju že to má složitost $O(N*log N)$ .... pokud tomu tak není tak budu rád když mě opravíte a napíšetemi jakou to vlastně má složitost...díky moc

vojta01 · 28. 11. 2010 13:26

Ahoj, bude to opravdu O(N * log N). Mě jen včera přišli divné ty 3 parametry u funkce "binarniHledani" - nejspíše to bude začátek a konec vyhledávací oblasti a hledaný prvek.

VojtechSejkora · 28. 11. 2010 14:57

↑ vojta01:
jj přesně tak to je:)

díky moc... to je pěkné z rádoby exponenciální udělat O(N*log N) :)...díky

Matematické Fórum

#1 27. 11. 2010 13:19 — Editoval VojtechSejkora (27. 11. 2010 14:28)

časivá složitost

Code:

Code:

#2 27. 11. 2010 16:28

Re: časivá složitost

#3 27. 11. 2010 18:50

Re: časivá složitost

#4 27. 11. 2010 22:44 — Editoval pizet (27. 11. 2010 22:46)

Re: časivá složitost

VojtechSejkora napsal(a):

#5 27. 11. 2010 23:34 — Editoval VojtechSejkora (27. 11. 2010 23:37)

Re: časivá složitost

#6 28. 11. 2010 13:26

Re: časivá složitost

#7 28. 11. 2010 14:57

Re: časivá složitost

Zápatí