《算法（第四版）》对加权 quick-union 算法的分析

[Higurashi]

《算法（第四版）》 1.5.2.7 节“对加权 quick-union 算法的分析”中有这样一个推论：

推论：对于加权 quick-union 算法和 N 个触点，在最坏情况下 find()、connected() 和 union() 的成本的增长数量级为 logN 。
证明：在森林中，对于从一个节点到它的根节点的路径上的每个节点，每种操作最多都只会访问数组常数次。

该推论基于前面的命题 H：

命题 H：对于 N 个触点，加权 quick-union 算法构造的森林中的任意节点的深度最多为 lgN 。

我不理解推论中所谓“最坏情况下的成本的增长数量级”。

find() 的成本（访问数组的次数）最多为 2 倍最大节点深度加一（命题 G ），对于 N 个触点，任意节点的深度最多为 lgN ，所以 find() 最多访问 2lgN + 1 次数组。要得到 find() 的增长数量级，应该要先得到成本随 N 的增长规律，可是，find() 访问数组的次数取决于输入，访问 2lgN + 1 次数组为最坏情况，所以这里或许该说“增长数量级最坏为 logN”？推论中“在最坏情况下”大概就是这个意思？

说实话，这似乎有些钻牛角尖了，但还是问一下，或许有不同的想法。谢谢。

加权 quick-union 算法：

public class WeightedQuickUnionUF
{
    private int[] id;      // 父链接数组（由触点索引）
    private int[] sz;      //（由触点索引的）各个根节点所对应的分量的大小
    private int count;     // 连通分量的数量
    public WeightedQuickUnionUF(int N)
    {
      count = N;
      id = new int[N];
      for (int i = 0; i < N; i++) id[i] = i;
      sz = new int[N];
      for (int i = 0; i < N; i++) sz[i] = 1;
    }
    public int count()
    {  return count;  }
    public boolean connected(int p, int q)
    {  return find(p) == find(q);  }
    public int find(int p)
    {  // 跟随链接找到根节点
      while (p ! = id[p]) p = id[p];
      return p;
    }
    public void union(int p, int q)
    {
      int i = find(p);
      int j = find(q);
      if (i == j) return;
      // 将小树的根节点连接到大树的根节点
      if   (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
      else                 { id[j] = i; sz[i] += sz[j]; }
      count--;
    }
}

命题 G：

quick-union 算法中的 find() 方法访问数组的次数为 1 加上给定触点所对应的节点的深度的两倍。