Content deleted Content added
m CE sentence case |
LouScheffer (talk | contribs) →Minimum spanning trees: Add a hash table scheme that is great in theory but too complex to be used in practice |
||
Line 45:
=== Minimum spanning trees ===
The [[expected linear time MST algorithm]] is able to discover the [[minimum spanning tree]] of a graph in <math>O(m + n)</math>, where <math>m</math> is the number of edges and <math>n</math> is the number of nodes of the graph.<ref>{{Cite journal |last1=Karger |first1=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411|doi-access=free }}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. An implementation is publicly available<ref>{{Cite web |last=Thiesen |first=Francisco |title=A C++ implementation for an Expected Linear-Time Minimum Spanning Tree Algorithm(Karger-Klein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine) |url=https://github.com/FranciscoThiesen/karger-klein-tarjan |access-date=2022-11-19 |website=[[GitHub]]}}</ref> and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 \cdot 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>
=== Hash tables ===
Researchers have found an algorithm that achieves the provably best asymptotic performance in terms of time-space tradeoff.<ref>{{cite arXiv
| last = Bender
| first = Michael
| date = 4 Nov 2021
| title = On the Optimal Time/Space Tradeoff for Hash Tables
| eprint = 2111.00602
| class = cs
}}</ref> But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."<ref>{{cite web |url=https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/ |title=Scientists Find Optimal Balance of Data Storage and Time}}</ref> and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”<ref>William Kuszmaul, as quoted in {{cite web |url=https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/ |title=Scientists Find Optimal Balance of Data Storage and Time}}</ref>
== References ==
| |||