リンクされたリスト表現を使用して各セットを表すとします。各ノードには、値、次のポインター、およびセットの代表へのポインターという 3 つのフィールドがあります。ヘッド、テール、カウント (セット内の要素の数) の 3 つのフィールドを持つ各セットの 1 つのインデックス オブジェクト (または代表) を維持します。
セットのユニオンの場合、要素ごとに新しいセットを作成し、それらのユニオンを取る必要があります。
n 要素の各作成操作には O(1) 時間がかかるため、合計 = O(n) です。
ここで、ユニオン中に、カウント数の少ないセットがカウント数の多いセットに追加されるように要素を結合します。そのため、n 個のセットの結合の時間計算量は O(n) かかります。
総時間計算量 = O(n) + O(n) /2n = O(1)。
したがって、私によると、ユニオン操作の時間の複雑さは O(1) である必要がありますが、どこでも O(n) と書かれています。なぜそうなのですか？