解决重复：T（n）= 2T（n / 2）+ 1 / log（n ^ 3）

Question

我需要找到此递归的上限和下限：T（n）= 2T（n / 2）+ 1 / log（n ^ 3）

有帮助吗？我只是想不通...

提前感谢

Answer 1

您可以使用Master's Theorem：

a = 2
b = 2

因此您拥有：

<<

大于

因此，我们有了Master定理的第一种情况，它暗示：

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9sYXRleC5jb2RlY29ncy5jb20vZ2lmLmxhdGV4P1QlMjhuJTI5JTNEJTVDdGhldGElMjhuJTI5In0”>

这只是一般的复杂性。对于确切的上下限，您应该使用递归或归纳法。