如何确定由该代码的效率描述的递推关系

Question

我是算法分析的新手。我在上找到了这个代码

boolean p (int s, int t, int n){
if (n == 1) {
if e(s, t) 
return true;
else
return false;
}
else {
for(i = 1; i <= n; i++) {
if (p(s, i, n/2) and p(i, t, n/2))
return true;
}
}
return false;    
}

如何确定此代码的效率所描述的递归关系？

假设函数e(i, j)返回一个布尔值并取O(1(

Answer 1

要找出n的递归关系，请考虑以下代码片段。

for(i=1;i<=n;i++) 
{
if (p(s,i,n/2) and p(i,t,n/2))
return true;
}

我们可以看到循环被执行n次。请注意，循环独立于参数s和t。

在每次执行过程中，此循环使用参数n/2调用函数p()两次。

还要注意，包括函数e(i,j)在内的其他操作只需要恒定的时间。

因此，该问题的递推关系为T(n) = 2n T(n/2) + O(1)。