Melyik a leggyorsabb algoritmus annak meghatározására, hogy egy gyűjteményből kiszedjük egy összegszám két összeadandóját?
Figyelt kérdés
Például van egy gyűjteményem, véletlenszerű számokkal, és meg akarom keresni ebben a gyűjteményben azt a két számot, amit ha összeadok akkor megkapom az én számomat. (azt az esetet, nem kell külön lekezelni, amikor nincs ilyen számpár, a lényeg az algoritmus maga). C++-ban kellene implementálni. A leglassabb módszer ha egyesével végigmegyek a számokon, de ennél hatékonyabb kellene.2019. júl. 18. 09:57
1/3 anonim 
válasza:
válasza:Csinálsz belőle egy másolatot halmazként és az eredeti gyűjtemény elemeit végigjárod, ellenőrizve, hogy a halmazban megvan a különbsége. O(n^2) helyett O(n) lesz a komplexitás.
2/3 anonim 
válasza:
válasza:Elso, (mar ha "halmaz" alatt hashtable-re gondoltal) ennek 2n lesz a helyigenye. "masolat" nelkul a legjobb, amit eddig talaltam: nlogn-es algoritmussal rendezed, utana elkezdesz iteralni ket mutatoval a sorozat ket szelerol, ha az aktualis par osszege nagyobb a keresettnel, lepteted az utolso mutatot balra, ha kisebb, lepteted az elsot jobbra, ez nlogn+n?
3/3 anonim válasza:
válasza:Halmaz alatt a Set containerre gondolok, aminek a megvalósítása valóban egy hashtable.
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!