#algorithm #asymptotic-complexity
#алгоритм #асимптотическая сложность
Вопрос:
В T (n) = 2T (n / 2) M (n), откуда берется 2 перед T . n / 2 потому что это деление, а M (n) линейно, но я не могу понять, для чего 2?
Ответ №1:
2, потому что вы выполняете операцию над двумя подмножествами. Смотрите основную теорему.
Ответ №2:
Рекуррентное соотношение похоже на то, что вы получаете при сортировке слиянием. Временная сложность была бы O (n log n)
Комментарии:
1. 2 — это потому, что вы работаете над двумя подзадачами равного размера, т. е
n/2
Ответ №3:
Это говорит о том, что временные затраты на задачу размера n возникают из-за разделения задачи пополам (т. Е. T (n / 2)) и ее решения для обеих половин (2 T (n / 2)) плюс некоторые затраты на исправление (т. Е. M (n)).
Итак, 2 — это потому, что вы делите проблему пополам и решаете обе половины.
Ответ №4:
2 представляет, сколько раз вы собираетесь вызывать повторяющуюся функцию.
Например, если у вас было дерево, у которого было 4 дочерних элемента, вы ожидали бы 4 для этого значения. В этом случае вы повторяетесь дважды.