tot*_*oto 9 c++ minimum-spanning-tree
http://en.wikipedia.org/wiki/Minimum_spanning_tree
我希望将最小生成树算法与最佳算法进行对比.有人知道我在哪里可以找到这些算法的C++实现吗？我叮叮当当地用谷歌搜索,但没有找到任何东西.如果这些算法是最好的,肯定必须在某处进行C++实现？
迄今为止最快的最小生成树算法是由David Karger,Philip Klein和Robert Tarjan开发的,他们发现了一种基于Borůvka算法和反向删除算法的线性时间随机算法.[2] [3] Bernard Chazelle最快的非随机算法基于软堆,即近似优先级队列.[4] [5] 其运行时间为O(mα(m,n)),其中m是边数,n是顶点数,α是Ackermann函数的经典函数逆.函数α增长非常缓慢,因此对于所有实际目的,它可以被认为是不大于4的常数; 因此Chazelle的算法非常接近线性时间.如果边权重是具有有界位长的整数,则确定性算法已知具有线性运行时间.[6] 对于一般权重是否存在具有线性运行时间的确定性算法仍然是一个悬而未决的问题.然而,Seth Petie和Vijaya Ramachandran已经发现了一种可证明最优的确定性最小生成树算法,其计算复杂性未知.[7]
我已经测试了Boost C++的图算法.
Edw*_*per 10
当维基百科页面显示"最快的最小生成树算法"时,它们的意思是具有最低渐近边界的算法 - 在这种情况下,O(mα(m,n)),定义了m,n和α就像你粘贴的报价一样.简而言之,这意味着对于非常大的输入值,对于C的某个值,所花费的时间总是受C*m*α(m,n)的限制.但请注意,C可能非常大 - 即,当应用于较小的输入值时,此算法可能比其他算法慢,即使它对于非常大的输入值比其他输入值更快.
当比较两个算法的渐近界限时,没有"测试"看哪个算法更快 - 你只需要证明每个算法的渐近界限,看看哪个更低.("渐近"是指输入大小变为无穷大时的行为 - 并且很难使用无限大小的输入值运行测试.)
但是请注意,有些情况下,你应该情况下不使用渐近最快的算法.如果"C"非常大,那么最好使用更简单的算法来处理较小的数据值.
我的猜测是你的算法可能会改进C,但不会改进渐近边界.但如果我错了,那么你应该把它提交给ACM!
有关详细信息,请参阅:http://en.wikipedia.org/wiki/Big_O_notation
| 归档时间： |
|
| 查看次数： |
7119 次 |
| 最近记录： |