algorithm - 最近接ペア アルゴリズムの効率

Question

T(n) = 2T(n/2) + M(n) では、T の前の 2 はどこから来ますか。n/2 は除算であり、M(n) は線形であるためですが、2 が何のためにあるのかわかりませんか?

Answer 1

2 (2 つのサブセットに対して操作を実行しているため)。マスター定理を参照してください。

Answer 2

再帰関係は、 Merge Sortで得られるものと似ています。時間の計算量はO(n log n)になります

Answer 3

これは、サイズ n の問題の時間コストは、問題を半分に分割 (つまり、T(n/2)) し、両方の半分 (2 T(n/2)) に修正コストを加えて解くことから生じることを示しています。 (すなわち、M(n))。

したがって、2 は、問題を半分に分割し、両方の半分を解決するためです。

Answer 4

2 は、繰り返し関数を呼び出す回数を表します。

たとえば、4 つの子を持つツリーがある場合、その値には 4 が期待されます。この場合、2 回繰り返されます。