fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
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?



#program #algoritmus #bonyolultság #komplexitás #nagy O
2020. júl. 24. 14:16
❮ 1 2 3 4 ❯
 11/34 anonim ***** válasza:
0%
Ja hogy nem akármit választhatsz hanem csak mindig elsőt vagy utolsót, sorry. Akkor ez erre a kérdésre egy felső becslést ad amit írtam. Még gondolkodom rajta csak el kell mennem most.
2020. júl. 26. 13:18
Hasznos számodra ez a válasz?
 12/34 A kérdező kommentje:
Mármint min gondolkodsz? A kérdést már az első válaszoló megválaszolta.
2020. júl. 26. 13:23
 13/34 anonim ***** válasza:
0%

"Mármint min gondolkodsz? A kérdést már az első válaszoló megválaszolta."


A válaszon , a megoldáson gondolkodom.

Én olyan választ nem látok ami megválaszolná a kérdést. Mivel támasztja alá hogy létezik rá O(y) megoldás?

2020. júl. 26. 15:45
Hasznos számodra ez a válasz?
 14/34 A kérdező kommentje:
Megoldást nem kérdeztem arra rájövök magamtól, csak a legjobb elérhető komplexitásra voltam kíváncsi.
2020. júl. 26. 16:03
 15/34 anonim ***** válasza:
0%
Semmi bizonyíték nincs rá hogy az a legjobb elérhető.
2020. júl. 26. 16:39
Hasznos számodra ez a válasz?
 16/34 A kérdező kommentje:

Szerintem belátható hogy ha nem vizsgálsz meg minimum y elemet akkor nem lehet megoldáshoz jutni, mert talán kihagyod pl. a legnagyobb elvehetőt. Ezt mondjuk egy rendezés megoldaná de akkor meg ugye semmiképpen nem lesz O(y)-nál jobb a komplexitás.

De lehet nincs igazam, ha találsz jobbat majd írd meg (ne a megoldást mert akkor megpróbálok arra is rájönni ha megvagyok az O(y)-al).

2020. júl. 26. 16:49
 17/34 A kérdező kommentje:
Eleve az összeg a kérdés és ahhoz ismernünk kell minden kiválasztott elemet. A kiválasztott elemek száma pedig y.
2020. júl. 26. 17:10
 18/34 anonim ***** válasza:
0%
Közel se biztos hogy ez elérhető, sőt arra fele hajlok hogy nem, ennél nagyobb futási idő lehetséges. Még összehasonlításon alapuló rendezésen se lehetséges jobb mint ordó n*log(n) n db elem esetében.
2020. júl. 26. 17:39
Hasznos számodra ez a válasz?
 19/34 anonim ***** válasza:
100%

#1-es vagyok.

#15 nem értem pontosan, hogy mire vársz bizonyítékot.

Arra, hogy O(y)-nál nem érhető el jobb komplexitás, vagy arra, hogy elérhető O(y)?


Ha előbbi igaz lenne, azzal azt mondanád, hogy [1, 100] (vagy lehet 0 az alja, nem tudom) intervallumból kiválasztott y db random szám összegének kiszámításához nincs szükség mind az y szám ismeretére. Ez elég abszurd (de végülis meggyőzhető vagyok, legalább ma is tanulok valami újat).


O(y)-hoz meg egyszerűen csak implementálj egy O(y) megoldást. Elég triviális, nincs szükség hozzá semmi különleges adatstruktúrára vagy algoritmusra.

2020. júl. 26. 17:39
Hasznos számodra ez a válasz?
 20/34 anonim ***** válasza:
0%
Várom azt az egyszerű O(y) idejű megoldást.
2020. júl. 26. 18:19
Hasznos számodra ez a válasz?
❮ 1 2 3 4 ❯

Kapcsolódó kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »



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!