Kezdőoldal » Számítástechnika » Programozás » Legjobb O komplexitás?

Legjobb O komplexitás?

Figyelt kérdé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?



2020. júl. 24. 14:16
1 2 3 4
 1/34 anonim ***** válasza:
43%
O(y) a legjobb, de nagy y esetén valszeg gyorsabb lenne egy O(x) megoldás.
2020. júl. 24. 14:45
Hasznos számodra ez a válasz?
 2/34 A kérdező kommentje:

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.

2020. júl. 24. 14:57
 3/34 A kérdező kommentje:
Ja rendezéssel nem is kapnánk jó eredményt :)
2020. júl. 24. 14:58
 4/34 anonim ***** 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?

2020. júl. 24. 21:18
Hasznos számodra ez a válasz?
 5/34 A kérdező kommentje:

"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.

2020. júl. 24. 21:26
 6/34 anonim ***** válasza:
Okés, igazad van, köszi.
2020. júl. 24. 21:28
Hasznos számodra ez a válasz?
 7/34 anonim ***** 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).

2020. júl. 24. 22:28
Hasznos számodra ez a válasz?
 8/34 anonim ***** válasza:
19%

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ő.

2020. júl. 25. 00:32
Hasznos számodra ez a válasz?
 9/34 anonim ***** válasza:
0%

"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ű.

2020. júl. 26. 12:19
Hasznos számodra ez a válasz?
 10/34 A kérdező kommentje:

"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.

2020. júl. 26. 12:33
1 2 3 4

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!