为什么 Tarjan 反而跑得比树剖慢？
查看原帖
为什么 Tarjan 反而跑得比树剖慢？
365751
Mr_罗楼主2024/11/6 11:11

RT，我测试了一下四种 LCA 算法的实际效率如下：

算法时间复杂度实际运行时间
倍增O(nlog⁡n)−O(mlog⁡n)\mathcal O(n\log n)-\mathcal O(m\log n)4.32s
树剖O(n)−O(mlog⁡n)\mathcal O(n)-\mathcal O(m\log n)1.61s
TarjanO(n)−O(n+m)\mathcal O(n)-\mathcal O(n+m)1.98s
dfs 序 + RMQO(nlog⁡n)−O(n)\mathcal O(n\log n)-\mathcal O(n)1.62s

可以看到倍增最慢（因为两边都有 log⁡\log），树剖和 RMQ 差不多（因为 n,mn,m 同阶），但是我不理解为什么理论最优的 Tarjan 反而实际不如带 log⁡\log 的优？

2024/11/6 11:11