Legjobb O komplexitás?
Az a feladat hogy sorban áll egymás mellett x darab ember akiknek ismert az életkoruk. Pontosan y darab lépést kell végrehajtanunk. Egy lépésben kiválasztunk egy embert a sor elejéről vagy a sor végéről és kivesszük a sorból. Az lépések végeztével a kivett emberek életkorát összeadjuk. Mennyi így a maximálisan elérhető összeg?
A sort egy tömb jelképezi ahol a tömb i-edik eleme az i-edik ember életkora. Maximum 100 000 ember állhat a sorban, egy ember maximum 100 éves lehet és y <= x.
Ha végigpróbálom a lehetséges elvételeket akkor ha jól számolok O(2^x) a komplexitás mert legrosszabb esetben x-szer választok 2 opció közül. Ezt mennyire lehet csökkenteni?
válasza:Közben rájöttem hogy a 2^x-en egy sima rendezéssel is sokat lehet javítani de akkor lehet annál is sokkal jobb.
Köszi.
válasza:Nekem elég zavaros a feladat leírása, de lehet csak azért mert már este van.
Miért kell végigpróbálni a lehetséges elvételeket?
Jelentse a 0 hogy előlről, az 1, hogy hátulról veszünk ki embert.
Ha jól értem, akkor te végig próbálnád pl. y = 4 esetén hogy
0000 (= első négy embert vesszük ki)
0001
0010
....
1110
1111
tehát mind a 2^4 = 16 variációt.
Miért nem jó az, ha minden lépésnél összehasonlítjuk az első és utolsó ember életkorát és a nagyobb életkorút vesszük ki? Mi az amit nem látok?
"Miért nem jó az, ha minden lépésnél összehasonlítjuk az első és utolsó ember életkorát és a nagyobb életkorút vesszük ki?"
Adott pl y = 2 és a következő tömb:
{1, 100, 3, 2}
A te logikád szerint elveszünk először 2-t aztán 3-at és így 5 lesz az eredmény. Holott lehetne 101 (ha elvesszük az 1-et és aztán a 100-at). A kérdés pedig az hogy mennyi a lehetséges maximum.
válasza:Ahogy az első is írta, O(y) a legjobb komplexitás.
Mindegy hogy milyen sorrendben veszegeted az embereket az elejéről és a végéről, a lényeg az lesz, hogy mennyit vettél el az elejéről (n) meg a végéről (y-n).
válasza:Először is, nem x-szer választasz két opció közül, hanem y-szor. Másodszor, nem minden választáshoz tartozik különböző összeg. Például egy n elemű tömbből választjuk az {1,2,3,n} elemeket; ekkor a <vége, eleje, eleje, eleje>, <eleje, vége, eleje, eleje>, <eleje, eleje, vége, eleje>, <eleje, eleje, eleje, vége> választás-sorozatok mind ugyanazt az összeget adják.
Összesen y+1 féle összeget tudunk összeválogatni (az elejéről választottak száma 0..y között alalkulhat), ezek maximumát kell megkeresnünk, ami ugyebár y darab összehasonlítással megtehető.
válasza:"Ja rendezéssel nem is kapnánk jó eredményt :)"
Miért ne kapnánk jó eredményt rendezéssel? Rendezed majd az első legnagyobbat veszed ahány darab kell. Ha a gyorsrendezést választjuk akkor az n elem esetén átlagos és legjobb esetben ordóba n*log(n) futási idejű. Legrosszabb esetben n^2 idejű. Akkor van legrosszabb eset, ha pont mindig rekurzívan úgy particionálja a tömböt a vezérelem, hogy mindig egyedül marad abba a partícióba. Ez ellen hogy ne lehessen legrosszabb esetet mondani van a randomizált változata a gyorsrendezésnek. Ez lehet úgy hogy összekevered az elemeket random, (ez megtehető lineáris időbe), majd gyors rendezed. Vagy pedig random generátorral választod ki mindig hogy melyik legyen a vezérelem.
Van az összefésülő rendezés, ennél általában gyorsabb a gyorsrendezés, de ez minden esetben ordó n* log n futási idejű.
A leggyorsabb általában az összehasonlítás alapú rendezések közül a gyorsrendezés. Viszont vannak nem összehasonlítás alapú rendezések is. Ilyen pl a leszámoló rendezés. Ez akkor jó, ha az elemek lehetséges értékének halmaza kicsi. Mondjuk legkevesebb 0 éves max 100 éves lehet egy ember, ekkor veszel egy 101 elemű tömböt kezdetben kinullázod. Majd végigmész az életkor tömbön és mindig hozzáadod eme tömb annyiadik eleméhez 1-et ahány éves az aktuális soron következő tag. Ekkor kapsz egy kvázi hisztogram tömböt. Ezt meg szabály szerint át kellene transzformálni egy rendezett tömbbé, pofon egyszerű csak for ciklussal amibe van egy for ciklus. Viszont itt ez se kell, ebből triviális kiválasztani, hogy mennyi az első m legnagyobb. Ez összességében ordó n komplexitású, vagyis lineáris idejű.
"Miért ne kapnánk jó eredményt rendezéssel?"
Ha rendezed a tömböt, akkor honnan tudod, hogy mit választhatsz? Hiszen mindig csak az első és utolsó elemet lehet az eredeti sorrend szerint.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!