Milyen bonyolultsági osztályba tartozik ez az algoritmus?
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?
De hát nem lesz a nagy ordóra hatással az első lépés egyik esetben sem. 8-as leírta hogy miért nem.
A tényleges futásidőre nyilván hatással lesz de nem az a kérdés.
válasza: válasza:Az m azért a leghosszabb string hossza, mert az O(m) a aszimptotikus felső korlátja a legjobb és a legrosszabb esetnek is. Utóbbi pedig az, hogy van legalább kettő m hosszúságú string. Ilyenkor egy olyan függvényt kell megadni, amihez legjobban közelít, de sosem éri el. Fel lehet írni O(m)-nél kisebbet is, de akkor fontos kihangsúlyozni, hogy az a legjobb eset.
#8-as és #11-es voltam.
Tehát ha azt mondjuk hogy O(n*m*logn) a bonyolultság ahol n a tömb mérete m pedig a 2. leghosszabb string hossza akkor az helytálló vagy nem?
Legrosszabb esetben ugye minden egyes string megegyezik a tömbben. Ekkor kell minden egyes string minden egyes karakterét megvizsgálnunk minden összehasonlításnál. Ilyenkor ugye a 2. leghosszabb string hossza egyenlő a leghosszabbéval tehát az állítás gyakorlatilag ekkor is igaz és minden más esetben is.
válasza:['a', 'bbbb' 'bbbc']
Ekkor a 2. leghosszabb 1, miközben össze kell hasonlítanod a két max hosszúságút.
válasza: válasza:#28/29 a kérdés már meg van válaszolva, O(n*m*logn).
Inkább csak hangosan gondolkozok már az m-en. De végülis már az is tiszta.
Köszönöm a válaszokat!
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!