Union-find-delete-algoritmien vertailua
Itäluoma, Sari (2015)
2015
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2015-06-08
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201506161731
https://urn.fi/URN:NBN:fi:uta-201506161731
Tiivistelmä
Union-find-algoritmi on tehokas ratkaisu erillisten joukkojen käsittelyongelmaan. Union-find-delete-algoritmissa siihen on lisätty poiston mahdollisuus. Esittelen tässä tutkielmassa useita union-find-algoritmeja ja union-find-delete-algoritmeja ja vertailen niitä teoreettisesti ja kokeellisesti.
Toteutin kolme erilaista union-find-delete-algoritmia, ja testasin niitä satunnaisilla syötteillä. Toteuttamani algoritmit ovat Ben-Amramin ja Yoffen algoritmi, aidon poiston algoritmi ja vajaan poiston algoritmi. Testieni perusteella vaikuttaa siltä, että asymptoottiselta aikavaatimukseltaan huonompi aidon poiston algoritmi toimii keskimäärin yhtä hyvin tai jopa paremmin kuin Ben-Amramin ja Yoffen algoritmi, jossa poisto tehdään vakioajassa.
Toteutin kolme erilaista union-find-delete-algoritmia, ja testasin niitä satunnaisilla syötteillä. Toteuttamani algoritmit ovat Ben-Amramin ja Yoffen algoritmi, aidon poiston algoritmi ja vajaan poiston algoritmi. Testieni perusteella vaikuttaa siltä, että asymptoottiselta aikavaatimukseltaan huonompi aidon poiston algoritmi toimii keskimäärin yhtä hyvin tai jopa paremmin kuin Ben-Amramin ja Yoffen algoritmi, jossa poisto tehdään vakioajassa.