最も近いペアの問題の時間計算量は、T（n）= 2T（n / 2）+ O（n）です。2T（n / 2）は、アルゴリズムが元のサイズの半分の2セットに適用されるという事実に由来することを理解していますが、なぜ残りはO（n）に出力されるのですか？ありがとう。
2 に答える
1
http://en.wikipedia.org/wiki/Closest_pair_of_points_problemを確認してください。これには、O(n) がどこから来るのか (Planar ケース) が明確に記載されています。
于 2013-02-25T22:15:01.953 に答える
-1
分割統治アルゴリズムは、再帰的な「分割」コンポーネントと、再帰的な結果がまとめられる「マージ」コンポーネントで構成されます。クローゼット ペアの線形 O(n) コンポーネントは、「分割」ステップの結果をマージされた回答にマージすることから得られます。
于 2013-02-25T22:26:57.140 に答える