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 » Milyen bonyolultsági osztályba...

Milyen bonyolultsági osztályba tartozik ez az algoritmus?

Figyelt kérdés

Két lépést hajtunk végre egy string tömbön, először megcseréljük minden string első és utolsó karakterét aztán rendezzük a tömböt csökkenő ABC sorrendben.

Ez milyen bonyolultsági osztály lesz?



#program #algoritmus #bonyolultság #string #rendezés
2020. aug. 8. 08:34
1 2 3 4 5 ❯
 1/46 anonim ***** válasza:
0%
Az elsőre nem kell algoritmus sem, csupán egy jól megírt sor, a második pedig az alap algoritmusok közé tartozik, egy programozónak az olyat kisujjból tudni kell. Vagyis ezek a legalapabb, legegyszerűbb feladatok, nincs is bonyolultsági szintjük.
2020. aug. 8. 09:04
Hasznos számodra ez a válasz?
 2/46 A kérdező kommentje:

Egyes ezekről van szó:

[link]

Hogy lehetséges hogy valaminek nincs bonyolultsága?

2020. aug. 8. 09:11
 3/46 anonim ***** válasza:
Legjobb esetben O(n log n)
2020. aug. 8. 09:14
Hasznos számodra ez a válasz?
 4/46 anonim ***** válasza:
Legjobb eset alatt arra gondolok, hogy a legoptimálisabb algoritmussal rendezed.
2020. aug. 8. 09:16
Hasznos számodra ez a válasz?
 5/46 anonim ***** válasza:
Keresés-re (rendezetlen tömbre) n*logn - nél jobb nincs. Az első lépés pedig 2 lépés csak. Tehet O(log n * n).
2020. aug. 8. 09:20
Hasznos számodra ez a válasz?
 6/46 anonim ***** válasza:
Tehát P-beli.
2020. aug. 8. 09:20
Hasznos számodra ez a válasz?
 7/46 A kérdező kommentje:

Osztálytársam azt mondja hogy az első lépés attól függ hogy milyen nyelvről beszélünk mert ha mutable a string (pl C++) akkor valóban csak egy csere ha viszont immutable (Pl Java, Python) akkor át kell másolni az egész stringet ahhoz hogy módosítsuk.

A rendezés pedig szerinte akkor lenne n*logn ha minden string 1 karakter hosszú lenne hiszen stringeket karakterenként hasonlítunk össze és nem mindegy hogy 1 karakter hosszú stringeket hasonlítunk össze vagy 1 millió karakter hosszúakat.


Miért nincs igaza? (gondolom ide hozzáértőbb emberek írnak egy gimnazistánál)

2020. aug. 8. 10:40
 8/46 anonim ***** válasza:
33%

Nem akarok más nevében beszélni, de szerintem itt mindenki félreértette, és a string tömb alatt karakterláncra gondolt, nem pedig karakterláncokból álló tömbre.

Ez esetben a rendezésnek a komplexitása O(n*log n), a stringek összehasonlítása pedig lineáris, így O(m), ahol m a leghosszabb string hossza. Így a teljes művelet O(m*n*log n).

Az átmásolást nem kell beleszámolni a komplexitásba, ugyanis O(a + b) = O(b), ha a < b. Itt az 'a' a másolás a 'b' a rendezés.

2020. aug. 8. 11:14
Hasznos számodra ez a válasz?
 9/46 A kérdező kommentje:

De ha egy karakterláncra gondoltam volna akkor hogy értelmezted azt hogy "megcseréljük minden string első és utolsó karakterét"?


"a stringek összehasonlítása pedig lineáris, így O(m), ahol m a leghosszabb string hossza"


Azt mondja ez nem igaz csak min(m1, m2) karaktert kell összehasonlítani mert ha eltérő hosszúak a stringek akkor a hosszabban nem kell minden karaktert megvizsgálni.

Ez nem így van? Végig kell nézni a hosszabb stringet?

2020. aug. 8. 11:26
 10/46 A kérdező kommentje:
Tehát ha van egy tömb amiben minden string 3 karakter hosszú kivéve egyet ami 3 millió karakter hosszú akkor minden egyes összehasonlításnál végig kell nézni 3 millió karaktert?
2020. aug. 8. 11:54
1 2 3 4 5 ❯

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!