三分查找的递归关系式

Question

3

三分查找的递推关系为T(n)= T(n/3) + 4，那么为什么递推关系中有4呢？因为在三分查找中，以3为底数的log N次方是分割次数，所以应该只有3个分割。

- Ved sinha

2

你对这个递归关系的来源是什么？数字4可能取决于特定实现以特定方式进行分析。 - templatetypedef

有一个问题，即二分查找和三分查找哪个需要更多的比较。在解决方案中给出了这个递归关系式，所以我正在思考，他们是如何得到4的。 - Ved sinha

2

那个递归关系对于通常称为“三分搜索”的算法不正确。你可能在想别的事情。请参阅：https://en.wikipedia.org/wiki/Ternary_search - Matt Timmermans

@Vedsinha，你能提供那个答案的直接链接吗？那似乎是错误的。 - templatetypedef

这是一个测试系列，所以如果我提供链接，它将需要凭据@templatetypedef。 - Ved sinha

@MattTimmermans 是的，我明白了，递归有误。 - Ved sinha

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yola · Accepted Answer

三分查找的递归关系是 T(n) = T(n/3) + O(1) 或者 T(n) = T(2n/3) + O(1)。这个 O(1) 中隐藏的常数取决于具体实现和分析方式，可能是 4 或者 3，或者其他值。根据主定理第二种情况，时间复杂度仍为 O(log n)。