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 » Mi a legjobb futásidő és...

Mi a legjobb futásidő és memória komplexitás ami elérhető ennél a Java feladatnál?

Figyelt kérdés

Van egy n elemű int tömb amiben 1-től n-ig fordulhatnak elő elemek. Lehet olyan ami többször és olyan ami egyszer sem. Vissza kell adni hogy hány elem nincs a tömbben.

Pl {4 1 1 3} tömbnél 1 az eredmény mert a 2 hiányzik.

{3 1 3 3 1}-nél 3 az eredmény, mert a 2 4 és 5 hiányoznak.

Azt gondoltam hogy legenerálom a számokat 1-től n-ig egy Setbe, végig megyek a tömbön és ha az aktuális elem nincs a Setben akkor növelem az eredményt eggyel.

Ez így asszem O(n) idő és O(n) memória. lehet valamelyiket tovább csökkenteni?



#programozás #memória #házi feladat #C++ #Java #Python #Visual C# #algoritmus #komplexitás #futásidő
2020. ápr. 28. 11:46
❮ 1 2
 11/17 anonim ***** válasza:
0%

Nem biztos, hogy jobb eredményt ad, de az is felhasználható, hogy ahány ismétlődő (nem új) értéket látunk bejáráskor, annyi fog hiányozni is.

{4,1,1,3} : Az 1-es újbóli megjelenése egyszer, vagyis a válasz: 1.

{3,1,3,3,1} : A 3-as kétszer bukkant fel újra, az 1-es egyszer, vagyis a válasz: 3

Egyszer elég végigmenni a tömbön, de egy másik tömbben gyűjteni kell, hogy mely értékek voltak eddig. Viszont ehhez elég egy bittömb, tehát az eredeti tömb méretének töredéke, ha az eredeti értéknek itt a bit indexet feleltetjük meg. Ennek kezelése persze növeli kicsit a valós futásidőt, ha az is számít.

2020. máj. 1. 12:43
Hasznos számodra ez a válasz?
 12/17 anonim ***** válasza:
0%
A futásidőbe egyébként elég sok apróság beleszámít, pl. "ha az aktuális elem nincs a Setben", igen, de érdemes ránézni, hogy az hogyan működik a háttérben. Persze van ilyen, hogy idő-memória komplexitás és a kettő megfelelő kompromisszuma, csak az elméleti érték javításakor akár szignifikánsan is ronthatunk a gyakorlati értéken.
2020. máj. 1. 12:45
Hasznos számodra ez a válasz?
 13/17 A kérdező kommentje:

Lehet nem egyértelműen fogalmaztam meg "legjobb futásidő és memória komplexitás"-t úgy értettem hogy legjobb futásidő komplexitás és legjobb memória komplexitás. Nem konkrét futásidő azt rengeteg dolog befolyásolja.

Tehát #1-es már megválaszolta a kérdést, köszönöm mégegyszer.

2020. máj. 1. 13:06
 14/17 anonim ***** válasza:
0%

Én is így értettem, csak egy összetett műveletet akkor sem szabad eleminek tekinteni, mint pl. a Set objektum "egyszeri" megszólítása.

Na mindegy, nem bonyolítom a dolgot. :)

2020. máj. 1. 14:48
Hasznos számodra ez a válasz?
 15/17 A kérdező kommentje:
Tehát akkor szerinted nem O(n) az idő komplexitás az én Set-es megoldásomnál? Vagy nem értem most mit akarsz mondani.
2020. máj. 1. 15:22
 16/17 A kérdező kommentje:
Hahó #14
2020. máj. 3. 13:50
 17/17 anonim ***** válasza:
Eltűnt a másik jóképességű válaszoló is az első oldalról, biztos csak ritkán gyakoriznak.
2020. máj. 3. 16:29
Hasznos számodra ez a válasz?
❮ 1 2

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!