runtime - 这些递归关系的运行时间

Question

您如何计算这些关系的紧密约束运行时间？

• T(n)=T(n-3)+n^2
• T(n) = 4T(n/4)+log^3(n)

对于第一个，我使用了给我 n^2 但不正确的替换方法，第二个我使用了 Masters Theorem 并得到了 nlog^4(n)，这也是不正确的。一个彻底的解释会很有帮助。谢谢！

Answer 1

对于第一次递归，我们可以通过递归树方法解决它

T(n)=T(n-3)+n^2

a）在这里我们看到子问题的数量是 n/3（每个 i 从 n 中减去 3，所以在 n/3 步中我们将到达最后一个子问题）。

b) 每个级别的成本为 n^2

因此时间复杂度大致为 (n/3)*n^2= (n^3)/3，即 O(n^3)

来到第二个递归关系

T(n)=4T(n/4)+log^3(n)

在这里我们不能应用 Master 定理，因为 n 和 log^3(n) 是不可比较的多项式时间，如果我们有类似 nlog^3(n) 的东西，我们可以应用 master 定理（严格对数界限的推论），因为它更大严格按日志时间

如果我在这里错了，请纠正我