Datové struktury a složitost algoritmů

Data Structures and Time Complexity of Algorithms

conference paper

Czech

Při řešení problémů operačního výzkumu, teorie grafů a dalších oblastí je potřebné navrhnout vhodný algoritmus, který řešení problému dokáže najít a navíc bude dostatečně efektivní. Řadu problémů lze řešit různými algoritmy, např. problém seřazení číselných položek podle vzestupného nebo sestupného uspořádání můžeme např. řešit algoritmem bublinového třídění s časovou složitostí O(n*n), kde n je počet seřazovaných položek, nebo mnohem sofistikovanějšími algoritmy QuickSort, HeapSort či MergeSort apod., které mají časovou složitost O(n log n). Efektivitu algoritmu nemusí však určovat jen jeho procedurální část, ale lze ji ovlivnit i volbou datových struktur. Z důvodu omezeného rozsahu se zaměříme pouze problém hledání minimální kostry grafu a jeho efektivní implementaci pomocí speciálních datových struktur disjunktní množina a binární halda

Solving problems of operations research, graph theory, and many others areas means to find a suitable and efficient algorithm. Many problems can be solved by various algorithms, e.g. sorting items in ascending or descending order can be solved by the BubbleSort algorithm with O(n*n) time complexity where n is a number of items, or by much more sophisticated algorithms such QuickSort, HeapSort or MergeSort that run O(n log n) time. The efficiency of algorithms, besides their procedural part, can also be controlled by used data structures. In this paper, we present a simple algorithm for solving the minimum spanning tree problem and their more efficient implementation using a binary heap and disjoint sets.

disjoint set, priority queue, binary heap, spanning tree

ŠEDA, M.

2005

30. 5. 2005

VŠB-TU Ostrava

Dolní Lomná u Jablunkova

80-248-0951-6

Sborník ze 14. semináře Moderní matematické metody v inženýrství 3mi

198

202

5