algorithm - 三元搜索的递归关系

Question

三元搜索的递推关系是 T(n)= T(n/3) + 4，4 的递推关系是怎样的，因为在三元查找中，它是以 3 N 为底的，所以应该只有 3 个分区？

Answer 1

三元搜索的递归关系为T(n) = T(n/3) + O(1)或T(n) = T(2n/3) + O(1)。隐藏在其中的常数O(1)取决于具体的实现以及如何进行分析。它可以是4or3或其他一些值。应用Master theorem 的案例 2你仍然有O(log n)。