@sengxian #3 虽然没有细看，也没有看懂，但知道这是在作均摊分析，似乎并没有直接分析“最坏”情形。但是在 https://oi-wiki.org/ds/dsu/ 的引用中，有一篇论文（ https://www.researchgate.net/publication/220430653_Worst-case_Analysis_of_Set_Union_Algorithms/link/0a85e53cd28bfdf5eb000000/download ）对此进行了分析，这篇论文中应该有想要的答案。显然对这个问题的解释并不是一两句话所能够说清楚的，有一种直观的理解方法当然最好，没有的话问题就到此为止。谢谢。

@sengxian #1 感谢回复。是的，更常见的似乎的确是按高度合并，但按大小合并也是一种可行（而且效率同样较高）的方法。我知道在该情况下深度不变，但这一点如何真正说明连续合并两棵树大小相等时是最坏的？能给些更详细些的提示吗？

FQYVG7

@YouRTBUG #3 嗯，再次感谢！

@YouRTBUG #1 感谢回复。因为我理解“处理 N 个触点和 M 条连接”的意思是：开始输入 N 个触点，互不相连（有 N 个分量），然后算法依照输入将触点逐个相连，连接到最后只剩 M 个分量。所以我说“最后剩下 M 条连接”。现在看来它实际的意思应该是：输入 N 个触点，且 N 个触点组成 M 个分量。将 M 个分量连起来需要调用 M 次 union ，加权 quick-union 的 union 函数最多访问数组 lgN 次，所以最多总共最多访问数组 MlgN 次，quick-find 的 union 函数至少访问 (N+3) 次数组，所以总共至少访问数组 M(N+3) 次。和书本上的说明接近，只是不知道为什么 MlgN 前面有一个常数 c ？另外 M(N+3) 次的总次数与 MN 还是有差别。

@ikesnowy #4 嗯，是。所以看来增长的数量级可用来给时间成本的增长快慢分类，比如两种不同的对数增长都属于对数级别、两种不同的线型级别也同属于线性级别（即使两者之间有比较明显的快慢区分）。也正因为如此，增长数量级相对于近似来说更“粗糙”，作者也在答疑中回复道：
“我们希望讨论的是给定成本模型下所有语句执行的准确频率，因为它们能够提供更多关于算法性能的信息，而且从我们所讨论的算法中获取这些频率是可能的。例如，我们可以说‘ThreeSum 访问数组的次数为～ N^3/2’，以及‘在最坏情况下 cnt++执行的次数为～ N^3/6’，它们虽然有些冗长但给出的信息比‘ThreeSum 的运行时间为 O （ N^3 ）’要多得多。”

@Higurashi #2 我想我知道了。当数据量很大时，log10N 和 log2N 之间的差别其实并不“显著”（可以到 https://www.geogebra.org/graphing?lang=zh_CN 看看），也正因如此，只有一个“对数级别”而不存在所谓“log10N 级别”或是“log2N 级别”。

@DaVinci42 #1 我懂了，非常感谢。有一个疑问是，对于一个增长数量级为 log10N 的算法，通过换底，其增长数量级也可以是 log2N ，我理解的增长的数量级，主要是用来反映算法时间成本的增长快慢（根据其图像的形状），而现在从图上看，log10N 和 log2N 的增长快慢差别似乎比较明显，或许该用来形容不同的算法，在这时候，如何理解“影响相对于 N 的变化来说，可以忽略”？

@lance6716 #3 嗯，我从 https://www.cnblogs.com/longjin2018/p/9854502.html 找到了更多的解释：

“设栈长度达到 N/2+1 时数组长度从 N/2 延长至 N 。连续的 push 操作使数组从长度 N 延长至 2N 是最坏的连续 push 情况。栈长度在 N/2+2 至 N 区间进行的 N/2-1 次 push 操作不会促使数组延长，此区间每次 push 对应一次数组元素的写访问。栈长度从 N 变为 N+1 时需要一次 push 操作和一次数组延长，一次 push 操作对应一次数组写操作，一次数组延长对应 4N 次数组访问。那么栈长度从 N/2+1 变为 N+1 需要进行的数组访问次数为 N/2+4N,push 操作次数为 N/2,均摊后每次 push 操作对应的数组访问次数为(N/2+4N)/(N/2)=9 。”

@lance6716 #1 感谢回复。是的，但不知道下面的理解是哪里出了问题：

比如 N 为 32 ，Stack 将在第 33 次 push() 操作时数组长度从 32 resize() 到 64 ，且此次 resize() 操作对数组的访问次数为 64 ，前一次数组加倍发生在第 17 次 push() 操作，数组长度从 16 resize() 到 32 ，resize() 操作对数组的访问次数为 32 。

那么，按照证明中的说法，对于第 33 次 push()，考虑使栈大小增长到 k 的最近 N/2-1=15 次 push() 操作（其中 k 在 N/2+2=18 到 N=32 之间），这 15 次 push() 操作之间只有一次 resize()，发生在第 17 次 push() 操作时，其访问数组的次数为 32 ，并不等于 4N=128 ，而 15 次 push() 操作，a[N++] = item; 对数组的访问为 15 次，也并不等于 N/2=16 次，更不用说取平均得到 9 。

另外按 DoublingStackOfStrings 的名称来看，它其实不应该实现泛型，而只支持 String 类型。

@GuuJiang #3
我大概懂了，现在做一点总结。
假设全都是二元运算符（包括一元运算符的情况类似）。
定义辅助符号<==>，读作“在该算法意义下等价”。如 s1 <==> s2 表示对于表达式 s1 和 s2 应用上述算法得到的结果相等。
第一步：证 X exp Y <==> X eval(exp) Y ，exp 表示形如 (v1 op v2) 的由 v1 、op 、v2 组成的子表达式（ v1 、v2 、op 分别表示两个字面值和一个操作符），X 、Y 分别表示算数表达式除 exp 后的前面部分和后面部分，且 X 中不包含右括号，eval(exp) 表示算法对子表达式 exp 求值后的结果。
在算法遇到 exp 中的右括号时，算法将 exp 中的 v1 、v2 弹出进行计算得到 eval(exp) 并将其入栈，因为 X 中不包含右括号，所以，算法解析 X eval(exp) Y 至 eval(exp) 入栈时，其结果与算法解析 X exp Y 至将 exp 求值后完全相同，所以 X exp Y <==> X eval(exp) Y 。
第二步：记 p(n) 为含有 n 对括号的合法表达式、p(n-1) 为算法对 p(n) 求值时遇到第一个右括号后出栈求解再入栈得到的新表达式（注意到此时括号会减少一对），由第一步的证明有 p(n) <==> p(n-1) <==> p(n-2) ... <==> p(1) <==> p(0)，不难知道算法能够正确处理不包括括号（只包含一个字面值）的 p(0)，所以算法能够正确处理 p(n)。
再次感谢。

@GuuJiang #1 感谢回复。为了防止误解，我觉得我还是先问清楚几个问题比较好。

1. 这里的“规约规则”是不是指“归纳奠基”？
2. X...<exp>...Y <==> X...eval(exp)...Y 是什么意思？
3. eval(p(n)) 是指？

@ynyounuo #1 感谢回复。的确应该是这样。所以 DoublingStackOfStrings 中的 Doubling 是“倍增”的意思，对应于 ResizingArrayStack 类中的 resize(2*a.length)。DoublingStackOfStrings 指的就是前文中的 ResizingArrayStack 。

@OysterQAQ #8 嗯，的确不处理问题也不大。

@Buges #2
感谢回复。我会试试看，虽然似乎并不那么好找，因为我看见有些库里面也并没有处理这里的情况。

@OysterQAQ #4
我没把注释说清楚，这里的意思实际上是指，比如传入一个在 float 中为 NaN 的整数 0b01111111100000000000000000000001 ，虽然返回的浮点值为 NaN ，但它并不能**保证**这个 NaN 的位模式为 01111111100000000000000000000001 （除非自己亲自验证一下）。

@OysterQAQ #1
感谢回复。意思是判断指数位是否为全 1 ，全为 1 则给出提示？这似乎并没有真正在用二进制“初始化”浮点数。