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
32/34 anonim 
válasza:
válasza:30.
Amit leírtál azt meglehet oldani sokkal gyorsabban és jobban. Ez sima bit eloltás. :).
33/34 A kérdező kommentje:
Nem is az volt a célom vele, hogy gyors legyen és jó, hanem, hogy rávezessem vele az O(y) megoldásra, de ezt le is írtam.
2020. aug. 4. 21:58
34/34 anonim 
válasza:
válasza:32.: tök hülyeséget írsz. Több minden van benne nem csak eltolás, továbbá az egy magyarázat volt a miértjére és 100 ezer elemű is lehetne a tömb.
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!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!