Bounds on Complexity when Sorting Reals
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00531334" target="_blank" >RIV/67985807:_____/20:00531334 - isvavai.cz</a>
Výsledek na webu
<a href="http://hdl.handle.net/11104/0310011" target="_blank" >http://hdl.handle.net/11104/0310011</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.46300/9106.2020.14.39" target="_blank" >10.46300/9106.2020.14.39</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Bounds on Complexity when Sorting Reals
Popis výsledku v původním jazyce
We derive the upper bounds on the complexity of the counting sort algorithm applied to reals. We show that the algorithm has a time complexity O(n) for n data items distributed uniformly or exponentially. The proof is based on the fact that the use of comparison-type sorting for small portion of a given data set is bounded by a linear function of n. Some numerical demonstrations are discussed.
Název v anglickém jazyce
Bounds on Complexity when Sorting Reals
Popis výsledku anglicky
We derive the upper bounds on the complexity of the counting sort algorithm applied to reals. We show that the algorithm has a time complexity O(n) for n data items distributed uniformly or exponentially. The proof is based on the fact that the use of comparison-type sorting for small portion of a given data set is bounded by a linear function of n. Some numerical demonstrations are discussed.
Klasifikace
Druh
J<sub>SC</sub> - Článek v periodiku v databázi SCOPUS
CEP obor
—
OECD FORD obor
10103 - Statistics and probability
Návaznosti výsledku
Projekt
<a href="/cs/project/LM2015068" target="_blank" >LM2015068: Výzkumná infrastruktura pro experimenty ve Fermilab</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Circuits, Systems and Signal Processing
ISSN
1998-4464
e-ISSN
—
Svazek periodika
14
Číslo periodika v rámci svazku
July
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
6
Strana od-do
276-281
Kód UT WoS článku
—
EID výsledku v databázi Scopus
2-s2.0-85087528484