本文介绍了三元搜索的递归关系的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
三元搜索的递归关系为T(n)= T(n/3)+ 4，递归关系如何，因为在三元搜索中它是以对数3 N为底的对数，因此应该只有3个分区?
The recurrence relation of ternary search is T(n)= T(n/3) + 4, How 4 is in recurrence relation, since in ternary search it's log to the base 3 N, so only 3 partitions should be there ?
推荐答案
三元搜索的递归关系是 T(n)= T(n/3)+ O(1)甚至是 T(n)= T(2n/3)+ O(1).隐藏在 O(1)中的常量取决于具体的实现方式以及进行分析的方式.它可以是 4 或 3 或其他一些值.应用主定理的情况2 ，您仍然有 O(logn).
Recurrence relation for ternary search is T(n) = T(n/3) + O(1) or even T(n) = T(2n/3) + O(1). The constant hidden in this O(1) depends on concrete implementation and how analysis was conducted. It could be 4 or 3, or some other value. Applying case 2 of Master theorem you still have O(log n).
这篇关于三元搜索的递归关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！