algorithm - 修剪和搜索的时间复杂度

Question

我阅读了很多关于 Prune 和 Search 算法的资料，甚至还询问了其中的一些内容以供确认。

这是一个很好的来源。然而，有些事情我很难理解。就像 Prune 和 Search 的时间复杂度：

有人可以为此提供一个简短的解释吗？

Answer 1

他们正在通过一些我不认识的奇怪方法解决递归 T(n) <= T(n/5) + T(3n/4) + Cn （C 是大 O 常数）。对缺少的基本案例和地板和天花板运算符取模，我们可以通过Akra-Bazzi或替换方法（这个答案）来解决它。

归纳假设是对于所有 n' < n，T(n') <= 20Cn'。然后

T(n) <= T(n/5) + T(3n/4) + Cn
     <= 20C(n/5) + 20C(3n/4) + Cn
      = 20C(4n/20) + 20C(15n/20) + Cn
      = 4Cn + 15Cn + Cn
      = 20Cn.