关于复杂度和常数
查看原帖
关于复杂度和常数
120324
Yansuan_HCl楼主2023/1/18 22:47

线段树一次 decrease-key 是 O(logn)O(\log n) 的,总复杂度是 O(nlog2n+nlogn)O(n\log^2 n + n \log n),而斐波那契堆可以做到 O(1)O(1) decrease-key, 总复杂度 O(nlogn+m+nlogn)O(n \log n + m + n \log n)。 然而斐波那契堆比线段树慢了 5s 多,这是 pb_ds 表现太差了吗?

2023/1/18 22:47
加载中...