Package for the RMedian algorithm
Project description
RMedian-Algorithm
A Python implementation of the RMedian algorithm.
The algorithm is presented in the paper Fragile Complexity of Comparison-Based Algorithms by Prof. Dr. Ulrich Meyer and others in 2019, which can can be found on arXiv.org.
It introduces the algorithm RMedian and also the concept of fragile complexity, i.e. the amount of times an element has been compared during the process of the algorithm.
The package was published on PyPI and tested on Travis CI.
Folder | Content |
---|---|
data | all experimental data as .csv files |
docs | scientific paper presenting the algorithm (old & new version) |
jupyter | Jupyter Notebook validation and test files |
poster | design for a poster explaining the algorithm |
src | Python source code |
tests | PyTest test files |
Algorithm
Complexity
- Runtime: RMedian requires linear work w(n) = O(n).
- Let k(n) = n_ε for 0 < ε ≤ 1/2. Then RMedian requires E(f_min(n)) = O(ε−1loglog(n)) comparisons for the minimum and E(f_rem(n)) = O(n_ε) for the remaining elements.
- Let k(n) = logn/loglogn. Then RMedian requires E(f_min(n)) = O(log(n)/loglog(n)) comparisons for the minimum and E(f_rem(n)) = O(log(n)/loglog(n)) for the remaining elements.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Close
Hashes for RMedian_Algorithm-0.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 506f5882f3272ff20a4a9c45a45a820c8930501364f88652cb8335f64c96c393 |
|
MD5 | 907e8d4d45fe2ef461c1213b7adad7d8 |
|
BLAKE2b-256 | 1f164914e8eed819d91f05c06d89ff5630827158f6b6d6417c9eca153e1bafe0 |