union-findアルゴリズムにおけるquick-findアルゴリズムの複雑さ

転載は出典を明記してください.http://www.codelast.com/
union-findアルゴリズムは、例えばコンピュータネットワーク内の2つのノードが接続されているかどうかを検出するために使用され、特定のサークル内の2人は間接的な友達関係があるかどうかなどを調べるために使用される.
quick-findアルゴリズムはunion-findアルゴリズムの多くの実装の中で最も簡単で、最も効率的ではない一種であり、その主な実現は以下の通りである.

public int find(int p) {
  return id[p];
}

public void union(int p, int q) {
  //     p    q  id     ，                     
  int pID = find(p);
  int qID = find(q);

  // p, q         ，      
  if (pID == qID) {
    return;
  }

  //      ，   p   q         ，           ，   ，   p                   q          （  ）
  for (int i = 0; i < id.length; i++) {
    if (id[i] == pID) {
      id[i] = qID;
    }
  }
  count--;
}

find()関数は、ポイントpの名前を検索します.union()関数は,2つの点pとqを規格化するために用いられ,それらが同一の連結成分の中にあるならば,任意の帰結効果は生じない.
記事のソース:http://www.codelast.com/
このようなアルゴリズムをquick-findと呼ぶのは、そのfind()の操作が速くて、ID配列に一回だけアクセスする必要があるからです.しかし、quick-findのunion()は、ID配列全体にアクセスする必要があるので、動作が遅いです.
実際、union()アクセス配列の回数は、少なくとも N+3、せいぜい 2 N＋1で、ここでNは点の個数である.
これはどうやって計算しますか?これから見てみます.
union()関数の最初の二つのfind()操作はどうしても逃げられないので、ここでは少なくとも2回のid配列を訪問しました.
に対する if(pID==qID) この文では、配列に対しては何のアクセスも行われていないので、最後のforサイクルは少なくともN＋1次配列にアクセスしたはずですが、これはどうやって計算されますか?
i 0サイクルからid.length(N)まで、全部でN回実行したので、forサイクルの中のif文は必ずN回実行します.だから、配列訪問は少なくともN回あります.1回足りないですが、どうやって来たのですか?
きっといい仕事があるから. id[i]==pID 成立(つまりpのあるその分量)なので id[i]==qID 少なくとも一回実行されますので、for循環アクセス配列の回数は少なくとも N＋1 回です.この場合、すべてのID配列のうち、1つだけの要素はpと同じ連結成分(つまりpという成分です.つまりpは「孤独」です.)であり、qのある連結成分に結合されます.
記事のソース:http://www.codelast.com/
では、union()の訪問配列の回数は、最大2 N＋1となりますが、これはどのように計算されますか?
ID配列において、q以外の全ての要素がpと同じ連結成分にある場合、if(id[i]=pID) この条件は成立します. N-1 このことは id[i]=qID 実行されます N-1 回、N回ifではどうしても実行されると判断しますので、forループでは配列にアクセスする回数は N+N-1=2 N-1 また、先の話ですが、union()関数の中で2つのfind()の操作は避けられないので、もう2回追加します.全部で2回です. 2 N-1+2=2 N+1 次数 
したがって、union()アクセス配列の回数は N+3 はい、 2 N＋1 間に
 
すべてのN個の成分が実は一つの連結成分の中にない場合、このunion-find問題を解く際にはN-1回のunion()関数を呼び出す必要があります. (N+3)(N-1) に相当する N^2 回の複雑さ
そこで証拠を得る.