Precise Estimates for the Time Complexity of Implementing Algorithms of Set-Theoretic Operations in Table Algebras

Autor:	I. S. Kanarskaya, A. S. Senchenko, D. B. Buy, V. N. Red'ko
Rok vydání:	2017
Předmět:	Set (abstract data type) Theoretical computer science General Computer Science Computer science Intersection (set theory) Computation Table (database) Randomized algorithms as zero-sum games Probabilistic analysis of algorithms Time complexity Algorithm
Zdroj:	Cybernetics and Systems Analysis. 53:1-11
ISSN:	1573-8337 1060-0396
Popis:	Algorithms implementing intersection, union, and difference in table algebras are investigated. Modifications of the most widespread algorithms reducing the amount of computations are proposed. Based on the complexities evaluated in the worst case and on the average for the modified algorithms, the fastest algorithm is found for each operation. A program that experimentally confirms theoretical estimates is developed.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e08867cd4e3d5c69c19feb15699d673c https://doi.org/10.1007/s10559-017-9901-2 Zobrazit plný text záznamu Full text from SpringerLink