эффективность алгоритма ближайшей пары

Question

В T (n) = 2T (n / 2) + M (n), откуда берутся 2 перед T. n / 2, потому что оно делится, а M (n) линейно, но я не могу понять, для чего 2?

Answer 1

2, потому что вы выполняете операцию на двух подмножествах. См. основную теорему .

Answer 2

2 представляет, сколько раз вы собираетесь вызывать повторяющуюся функцию.

Например, если у вас есть дерево с 4 дочерними элементами, вы ожидаете 4 для этого значения. В этом случае вы повторяетесь дважды.

Answer 3

Это говорит о том, что затраты времени на проблему размера n связаны с делением задачи пополам (т. Е. T (n / 2)) и ее решением для обеих половин (2 T (n / 2)) плюс некоторое исправление стоимость (т. е. M (n)).

Итак, 2 означает, что вы делите задачу пополам и решаете обе половины.

Answer 4

Отношение повторения похоже на то, что вы получаете в Сортировка слиянием .Временная сложность будет O (n log n)