1

具有自平衡二叉搜索树的 Dijkstra 算法的复杂度为 O(e * log(n))。这是否意味着在统计中间，e=100 和 n=25 的寻路查询花费的时间是 e=50 和 n=25 的寻路查询的两倍。

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

4

2 回答 2

0

我认为这里的数学很简单，O(E * log(N))平均运行时间与 E 成正比。 O(n) 实际上可以是O(n) + C，所以如果小n而显着C，n*2则不会慢两倍，而是更少：(2n + C) / (n + C)。

于 2013-03-06T14:32:31.167 回答
0

我想你可能会觉得它很有趣： http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=complexity2

检查标题“递归树”

于 2013-03-06T16:13:48.963 回答