求问复杂度

学术版

OIer_Hhy @ 2024-11-29 20:03:05

rt，祝看到这条消息的人 NOIp rp++ 拿到省一。

问：

  • __builtin_popcount(n) 的复杂度？

  • __gcd(n,m) 的复杂度？

  • 为什么并查集的复杂度是 O(nlogn) ？

by Walrus @ 2024-11-29 20:07:40

这个虽然可用，但是这些函数还不是有底层实现机制。所以我认为

  1. log
  2. log
  3. 并查集路径压缩后是 O(n \alpha )，好像是这么写的吧，我记得这大概只有 5 倍常数，但是带 log 我不理解

by mayike @ 2024-11-29 20:08:20

@OIer_Hhy

  1. 不知道
  2. \log(\min(n,m))
  3. 路径压缩了是 n\log n，路径压缩且启发式合并是 O(n)\times 反阿克曼

by Walrus @ 2024-11-29 20:10:16

奥对哦是启发式合并带反阿克曼

by strcmp @ 2024-11-29 20:11:01

$\Theta(\log n)$。 带启发式合并/按秩合并，不路径压缩，显然可以分析到 $\Theta(n \log n)$。只分析启发式合并的话，大概就是只会对 $\text{siz}$ 小的一边增加 $1$ 的深度，每个结点增加 $1$ 的深度，所在联通块大小至少乘二，所以复杂度 $\Theta(n \log n)$。 路径压缩的复杂度分析困难，建议自己搜索。只路径压缩的复杂度是 $\Theta(m \log_{1 + \frac{m}{n}}n)$。路径压缩且启发式合并的并查集复杂度是 $\Theta(m \alpha(n))$，并不是 $n \log n$，$\alpha$ 是反阿克曼函数，你可以认为现实范围内 $\alpha(n) \le 5$。

by OIer_Hhy @ 2024-11-29 20:12:34

thx。

by strcmp @ 2024-11-29 20:14:02

@OIer_Hhy 随机情况下只路径压缩的并查集期望复杂度是 \Theta(m \alpha(n)) 的，实际情况下一般只路径压缩就够了。

by Joe2011 @ 2024-11-29 20:15:13

@OIer_Hhy

  1. log
  2. log
  3. O(n\alpha(n))$，近似$O(n)

by Joe2011 @ 2024-11-29 20:16:47

@OIer_Hhy

1.是这样的：这里

by strcmp @ 2024-11-29 20:17:11

__builtin_popcount 复杂度绝对不会是 \Theta(\log n)，最多 \Theta(\log \log n)，看具体实现。

by strcmp @ 2024-11-29 20:21:06

@Joe2011 这哥们不是自己实现了个 __builtin_popcount 吗/lh

实际 __builtin_popcount 不可能实现这么劣吧。

| 下一页