基于复杂度的Dijkstra算法平均运行时间变化

具有自平衡二叉搜索树的Dijkstra算法的复杂度为O（e * log（n））。这是否意味着在统计学中，e = 100和n = 25的寻路查询比寻找e = 50和n = 25的查询的寻路时间增加一倍。基于复杂度的Dijkstra算法平均运行时间变化

这个问题有点困难，我的观点是关于统计平均运行时间变化的相对比较。

2013-03-06 Tim91

标题完全是误导，试图重新制定它。 – Andrey 2013-03-06 14:22:30

我觉得数学很简单这里，与O(E * log(N))平均运行时间是成比例的大肠杆菌O（N）可在现实中O(n) + C，所以用小n和显著C的n*2会不会两次慢，但少：(2n + C)/(n + C) 。

2013-03-06 14:32:31 Andrey

我真的不明白你答案的第二部分。在第一部分中，您说运行时间与边的数量成正比。所以这意味着加倍的边缘会使平均运行时间加倍。在你的答案的第二部分中，你指的是n * 2，这是指节点数加倍，对吧？ – Tim91 2013-03-06 15:54:48

@ Tim91第二部分我使用泛型n作为变量。 – Andrey 2013-03-06 17:05:46

检查标题“递归树”

2013-03-06 16:13:48 Hammer

回答