Publication detail
Data Structures and Time Complexity of Algorithms
ŠEDA, M.
Czech title
Datové struktury a složitost algoritmů
English title
Data Structures and Time Complexity of Algorithms
Type
conference paper
Language
cs
Original abstract
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
Czech abstract
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
English abstract
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.
Keywords in English
disjoint set, priority queue, binary heap, spanning tree
RIV year
2005
Released
30.05.2005
Publisher
VŠB-TU Ostrava
Location
Dolní Lomná u Jablunkova
ISBN
80-248-0951-6
Book
Sborník ze 14. semináře Moderní matematické metody v inženýrství 3mi
Pages count
5
BIBTEX
@inproceedings{BUT15921,
author="Miloš {Šeda},
title="Datové struktury a složitost algoritmů",
booktitle="Sborník ze 14. semináře Moderní matematické metody v inženýrství 3mi",
year="2005",
month="May",
publisher="VŠB-TU Ostrava",
address="Dolní Lomná u Jablunkova",
isbn="80-248-0951-6"
}