Feladatok

  1. A négyzetes tömb újraszámolása négyzetes bonyolultságú. Gyorsítsa fel a módszert azzal, hogy nem számolja újra minden összevonás után a t tömböt, hanem annak tartalma alapján határozza meg elemeinek értékeit az összevonás után. Tipp: a tömb i és j sorainak/oszlopainak összevonása után a kisebb indexűt frissítse a másik alapján! A nagyobb indexű helyére átmásolhatja a tömb utolsó sorának/oszlopának értékeit, így a tömb mérete eggyel csökken az összevonás után.

  2. Az összevonás variánsa segédosztályában alkalmazott vektor helyett használjon kupacot! Hasonlítsa össze a futási eredményeket!

    Az összevonás kiválasztásakor használja a vektort, vonjon össze az első eleme szerint! Ha véletlenül ez az elem már nem létezik, mert korábban már összevonásra került, akkor a dobja ki az elemet a vektorból, és folytassa a következővel! Ha a vektor kiürült, határozza meg újra a t elemeit, és vele együtt a vektort újra töltse fel!

  3. Az előző feladat megoldásában tartsa karban a vektor elemeit, ha összevonás során valamely elem eltűnik, mert összevonásra került, törölje a vektorból is! Hasonlítsa össze a futási eredményt az előző feladat megoldásának futásai eredményeivel!

  4. A t tömb helyett használjon egy olyan adatszerkezetet, melynek elemei egyrészt hatékonyan elérhetőek a koordinátáik alapján, másrészt az elemek értéke szerint rendezettek vagy kupacként viselkednek. Legyen lehetőség az adatszerkezetben elemek törlésére! Ezzel az adatszerkezettel implementálja az összevonás módszerét! Az adatszerkezet eredeti felépítése négyzetes bonyolultságú, majd ezután minden egyes összevonás lineáris bonyolultságú lesz!

  5. Az előbbi javításokat alkalmazza a kombinált módszerre! Hasonlítsa össze a futási eredményeket!

  6. A max-min módszernél lineáris bonyolultságú az egyes dimenziókhoz tartozó konfliktusok meghatározása. Implementálja azt a gyorsítást, amely figyeli, hogy történt-e változás a legutóbbi meghatározás óta, szükséges-e az értékek frissítése, vagy sem.