Publication detail

Datové struktury a složitost algoritmů

ŠEDA, M.

Original Title

Datové struktury a složitost algoritmů

English Title

Data Structures and Time Complexity of Algorithms

Type

conference paper

Language

Czech

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

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.

Key words in English

disjoint set, priority queue, binary heap, spanning tree

Authors

ŠEDA, M.

RIV year

2005

Released

30. 5. 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 from

198

Pages to

202

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",
  pages="5",
  publisher="VŠB-TU Ostrava",
  address="Dolní Lomná u Jablunkova",
  isbn="80-248-0951-6"
}