如何查找递归二进制搜索的运行时间？

对于以下每个步骤，设T（n）为运行时间。查找T（n）的（即，发现F（N）的次序，使得T（N）∈（F（N））。如何查找递归二进制搜索的运行时间？

Procedure BinarySearch(table T [a . . . b], int k): 
if a > b then 
    return -1 
end if 
middle ← ⌊(a + b)/2⌋ 
if T [middle] = k then 
    return middle 
end if 
if k < T [middle] then 
    return BinarySearch(T [a . . .middle], k) 
else 
    return BinarySearch(T [middle . . . b], k) 
end if

我知道如何找到简单的功能，但由于这个运行时间包括递归调用，所以我有麻烦。

来源

2014-01-23 user2264035

如果你想想看一点点，那么你可以直观地推论出它是'O（log2（n））'。 – 2014-01-23 18:49:02

假设你有T（n）。那么对于每个T（n），你把它分成两半，所以T（n/2）。你能在h分裂n吗？阿尔夫？请参阅@ H2CO3的评论。 –

您的伪代码中有一个错误。令a = 1和b = 2，并且T [2] = k。那么中间=（a + b）/ 2 = 1且k> T [1]。你将递归调用BinarySearch（T [1 ... 2]，k）。你最好把你的伪代码改成“return BinarySearch（T [a ... midmid-1]，k）”和“return BinarySearch（T [middle + 1 ... b]，k）”。正如你已经检查过T [中]，再次检查它没有任何意义。 –

This link（在页面底部）描绘了解决二进制搜索算法的递推关系的一个非常明确的方式。

来源

2014-03-14 22:20:39

如何查找递归二进制搜索的运行时间？

回答

相关问题