algorithm - 没有 f(n) 的递归主定理

Question

Master 定理可以应用于 f(n) 为零的递归，例如：T(n)=2T(n/3) + 0? 如果是，将如何解决？考虑到这一点，它会花费恒定的时间T(1)=1吗？

Answer 1

T(n)=2T(n/3) + 0

a = 2, b =3, c = 0 因为我们在寻找 n ^c，因为我们有零作为常数，所以这里只能使用 n ⁰。所以 T(n) 以 n ^{log ₃ 2}为界，大约。n ^0.63。