如何计算以下算法的时间复杂度。我尝试过，但由于递归调用而感到困惑。
power (real x, positive integer n)
//comment : This algorithm returns xn, taking x and n as input
{
if n=1 then
return x;
y = power(x, |n/2|)
if n id odd then
return y*y*x //comment : returning the product of y2 and x
else
return y * y //comment : returning y2
}
可以用简单的步骤来解释一下。
为了弄清楚递归函数的时间复杂度，您需要计算将要根据某些输入变量进行的递归调用的次数N。
在这种情况下，每个调用最多进行一个递归调用。调用次数约为O（log 2 N），因为每次调用都会减少N一半。
递归函数的其余部分为O（1），因为它不依赖N。因此，您的函数的时间复杂度为O（log 2 N）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句