蒟蒻刚学OI求解可并堆
查看原帖
蒟蒻刚学OI求解可并堆
13197
zhendelan楼主2020/11/2 10:54

这题可并堆的时间复杂度是错的吗?
因为每次查答案都要走到堆的根。但是堆的深度是O(n)O(n)的级别的。

也就是说不能路径压缩,时间复杂度不是错的吗。。。。
求大佬解答。

而且删除堆中的任意一个数(并非一定是堆顶)这种操作的复杂度在oi-wiki上也是暴力跳的。这样不也是O(n)O(n)吗。。

2020/11/2 10:54
加载中...