@思念前生

第一篇:

  1. 带路径压缩的并查集,单次操作平均复杂度接近 O(1).

在算法竞赛的实际代码中,即便不使用启发式合并,代码也往往能够在规定时间内完成任务。在 Tarjan 的论文[1]中,证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是 O(mlogn)O(m\log n) 。在姚期智的论文[2]中,证明了不使用启发式合并、只使用路径压缩,在平均情况下,时间复杂度依然是 O(mα(m,n))O(m\alpha(m,n)) 。——引自 OI-wiki

而且每一篇的排版都太丑了吧……

2020/8/15 22:39
175829