今日が期限の課題について、どのソリューションがリリースされているかについて質問がありますが、正解がわかりません。この質問は、パフォーマンスを向上させるために加重和集合アルゴリズムを利用する素集合フォレストの形式で素集合の最良の場合のパフォーマンスを扱います (ツリーの小さい方のルートは、2 つのツリーのうち大きい方のルートに子として接続されます)。 ) ただし、パス圧縮アルゴリズムは使用しません。
問題は、n 個のシングルトン ノードで (n-1) ユニオン操作を実行し、任意の順序で m>=n 検索操作を実行した場合の最良のケースのパフォーマンスが Omega(m*logn) であるかどうかであり、ソリューションは次のように正しいことを確認します。
n-1 ユニオンのシーケンス S の後に m >= n 検索が続き、Omega(m log n) 時間かかります。シーケンス S は、深さ Omega(log n) のツリーを構築するシーケンス n-1 Unions で始まります。次に、m>=n の検索があり、それぞれがそのツリーの最も深い葉に対応するため、それぞれに (log n) の時間がかかります。
私の質問は、下限が Omega(m*logn) であることを証明するのはなぜですか? それは、境界が Omega(m*logn) であり、すべての入力に対してそれを証明していない場合の孤立した例ではありませんか? 主張を反証するときは反例を1つだけ示す必要があると確信していますが、その正しさを証明するには、可能なすべての入力の述語を証明する必要があります.
私の回答では、2 つのシングルトン ノードを一緒に結合することから始める場合があるという事実を指摘しました。次に、n 個のノードすべてを結合するまで、3 つのノードが同じ親を共有する別のシングルトンをその 2 ノード ツリーに結合し、次に別のノードを結合します。次に、n-1 個のノードがすべて同じ親を指しているツリーができます。これは基本的に、パス圧縮を使用した場合に得られる結果です。次に、すべての FIND が O(1) 時間で実行されます。したがって、(n-1) 個のユニオンと m>=n 個の検索のシーケンスは、最終的に Omega(n-1+m) = Omega(n+m) = Omega(m) になります。
これは、Omega(m*logn) の限界がきつくなく、したがって主張が正しくないことを意味していませんか? Big-O/Omega/Theta を完全に理解していないのではないかと思い始めています :/
編集：質問を修正して、少し明確にしました
EDIT2:これが元の質問の提示方法と解決策です (ガンバリーノと他の男が完全にでっち上げであることに気付くのに少し時間がかかりました; 筋金入りのイタリア人教授)
