Я изучаю анализ времени алгоритмов, и у меня есть вопрос о следующей проблеме:
Допустим, у нас есть проблема размера n, и мы можем использовать алгоритм, который решает проблему, разделив ее на n Подзадачи ^ (1/2) (каждая имеет размер n ^ (1/2), рекурсивно решая каждую подзадачу, а затем комбинируя решения за линейное время.
Моя цель - найти временную сложность этого алгоритм. Я считаю, что мне нужно решить одно из этих двух рекурсивных уравнений: T (n) = n ^ (1/2) * T (n ^ (1/2)) + n, T (n) = n ^ ( 1/2) * T (n ^ (1/2)) + O (n). Однако я не знаю, какой именно. Не могли бы вы сказать мне различия между этими двумя?