关系的时间复杂度 T(n) = T(n-1) + T(n/2) + n
time complexity of relation T(n) = T(n-1) + T(n/2) + n
关系
T(n) = T(n-1) + T(n/2) + n
我可以先求解给出 O(n^2) 的项 (T(n-1) + n)，然后求解项 T(n/2) + O(n^2) 吗？
根据同样给出 O(n ^ 2) 的主定理还是错误的？
我不认为你的做法在一般情况下是正确的。当您丢弃 T(n/2) 项来计算 T(n-1) 项的复杂性时，您最终低估了 T(n-1) 项的大小。
具体反例：
T(n) = T(n-1) + T(n-2) + 1
你的技术也将为此提出 T(n) = O(n^2)，但真正的复杂性是指数级的。
不，你不能用母定理来解决它。
您需要使用 Akra–Bazzi method 来解决它，这是对著名主定理的更清晰的概括。
主定理假定子问题大小相等。
主定理涉及形式
T(n) = a T(n/b) + f(n) , where a>=1, b>1.
我不是在这里导出解决方案的步骤，以便您解决它。如果您在解决相同问题时还有其他问题，请在下面发表评论。祝你好运...
关系
T(n) = T(n-1) + T(n/2) + n
我可以先求解给出 O(n^2) 的项 (T(n-1) + n)，然后求解项 T(n/2) + O(n^2) 吗？
根据同样给出 O(n ^ 2) 的主定理还是错误的？
我不认为你的做法在一般情况下是正确的。当您丢弃 T(n/2) 项来计算 T(n-1) 项的复杂性时，您最终低估了 T(n-1) 项的大小。
具体反例：
T(n) = T(n-1) + T(n-2) + 1
你的技术也将为此提出 T(n) = O(n^2)，但真正的复杂性是指数级的。
不，你不能用母定理来解决它。
您需要使用 Akra–Bazzi method 来解决它，这是对著名主定理的更清晰的概括。
主定理假定子问题大小相等。
主定理涉及形式
的递归关系
T(n) = a T(n/b) + f(n) , where a>=1, b>1.
我不是在这里导出解决方案的步骤，以便您解决它。如果您在解决相同问题时还有其他问题，请在下面发表评论。祝你好运...