n 個の単一ノード ツリーがあり、m 個の集合演算が見つかり (注: 結合が以前に行われたと仮定すると、結合はありません)、パス圧縮のみを使用する場合、これには O(m) 時間がかかるというのは本当ですか? 私はこれを証明しようとしてきましたが、そうではないようです。ユニオンはランクによるユニオンを使用しなかったため、検索セットには最大で O(n) の時間がかかる場合があります。しかし、m 個の検索セットを O(m) 時間で実行することはまだ可能ですか?
n 個の単一ノード ツリーがあり、m 個の集合演算が見つかり (注: 結合が以前に行われたと仮定すると、結合はありません)、パス圧縮のみを使用する場合、これには O(m) 時間がかかるというのは本当ですか? 私はこれを証明しようとしてきましたが、そうではないようです。ユニオンはランクによるユニオンを使用しなかったため、検索セットには最大で O(n) の時間がかかる場合があります。しかし、m 個の検索セットを O(m) 時間で実行することはまだ可能ですか?