algorithm - 使用主定理的推广解决方程

Question

我请求帮助解释证明是如何工作的。我看过它的例子，但很难理解它。

证明以下

方程的解

T(n) = aT(n/b) + Θ(n ^k log ^p n) 其中 a ≥ 1, b > 1, p ≥ 0

• T(n) = O(n ^{log _b a} ) 如果 a > b ^k

• T(n) = O(n ^k log ^p+1 n) 如果 a = b ^k

• T(n) = O(n ^k log ^p (n)) 如果 a < b ^k

这是问题的屏幕截图，格式更好

这是主定理的推广。

Answer 1

对于某些 x =log(n)/log(b) 有 n=b ^x。将方程除以^x

T(b ^x )/a ^x = T(b ^x-1 )/a ^x-1 + Θ((b ^k /a) ^x ·x ^p ·log ^p b)

对于 m < x ，项 m ^p ·q ^{m的总和是}

• 对于 q < 1，以常数为界
• 对于 q = 1，像 x ^{p+1一样增长}
• 由最后一项 x ^p ·q ^x支配，当q > 1

识别 q=b ^k /a 并代回给出结果

• 对于 a < b ^k： T(b ^x )=O(a ^x )，或 T(n)=O(n ^{log _b a} )
• 对于 a = b ^k： T(b ^x )=O(x ^p+1 ·a ^x )，或 T(n)=O(n ^{log _b a} ·log ^p+1 n )
• 对于 a > b ^k： T(b ^x )=O(x ^p ·b ^kx )，或 T(n)=O(n ^k ·log ^p n)