Я написал рекурсивный алгоритм, который работает в Θ(n).
Одним из рекуррентных уравнений для n > 0 является T(n) = T(v) + T(n - 1 - v) + c, где c — константа, а v — переменная, которая может принимать значения в фиксированном диапазоне n > v > 0.
Как мне дальше решить или правильно упростить это уравнение?
Просто многократно расширяйте непостоянный термин:
Серия заканчивается, когда:
Это означает, что 
T(v) сократится со знаменателем в N.
v может меняться при каждом рекурсивном вызове этого типа (в зависимости от топологии поддерева, в котором выполняется вызов)? Или предполагается, что v будет константой во время одного выполнения алгоритма?
- person George; 02.08.2016
Vi, а сумма T(Vi) все равно отменит знаменатель.
- person ; 02.08.2016
В комментариях вы описали поведение вашего алгоритма следующим образом: он выполняет постоянный объем работы над пустым деревом и в противном случае выполняет постоянный объем работы, а затем рекурсивно обрабатывает левое и правое поддеревья. Вместо того, чтобы описывать время выполнения рекуррентным отношением, подобным тому, которое вы описали, вы можете учитывать время выполнения по-другому: проделанная работа прямо пропорциональна количеству узлов в дереве, поскольку вы можете взимать плату за каждую единицу выполненной работы. к определенному узлу. В результате общее время выполнения составляет O(n).
vприближается к середине диапазона(0, n), сложность будетO(log(n)), а когда значениеvнаходится в углу этого диапазона, сложность будетO(n). - person Shubham schedule 24.07.2016T(n) = T(n-L-1)+T(n-R-1)+c, гдеL— это левое поддерево (с корнем в левом дочернем узле), аR— это правое поддерево (с корнем в правом дочернем узле) обрабатываемого корневого узла. ПосколькуR = n-1-LиL = n-1-R(гдеn— общее количество узлов в поддереве, а1— корневой узел), уравнение можно упростить доT(n) = T(n-L-1) + T(n-(n-1-L)-1) + c = T(n-L-1) + T(L) + c, что эквивалентноT(n) = T(R) + T(n-1-R) + c. - person George schedule 25.07.2016