algorithm - 使用递归、使用 while 循环或两者，哪种执行权力(在时间复杂度方面)的方法更有效？

Question

我看过“分而治之”算法的代码示例(或者，至少我认为是“分而治之”)——一组通用示例倾向于使用递归，而另一组示例使用递归while 循环。

这是递归的例子:

...
if (exponent%2==0) 
{ 
return Power(base*base, exponent/2); 
} 
else if (exponent%2==1)
{ 
    return base*Power(base*base, exponent/2); 
} 
...

并且，这是 while 循环示例:

...
while (exponent>1)
{
    if (exponent%2 == 1)
        result *= base;
    exponent/=2;
    base *= base;
}
...

在这两种情况下，看起来它们确实是用相同数量的操作执行的。这两种方法似乎都采用的操作数受限于 T(exponent) = Θ(log_2(exponent)) 的上限函数。除非我的分析有误，否则我看不出一种方法比另一种方法更快。我认为递归方法在空间复杂度方面不如 while 循环方法有效，因为递归方法的空间复杂度为 2*(log_2(exponent))(如果该分析是正确的)。

while 循环方法的唯一优点是它的空间要求较低吗？

Answer 1

假设您使用的编译器是健全的，那么是的......较低的空间需求是唯一的优势。

请注意，大多数编译器都允许有效处理 tail recursion ，当函数仅在执行的最后一步调用自身时会发生这种情况(有关示例，请参见文章)。如上所述，您的递归算法不是尾递归的，因为返回之前采取的最后一步是乘法(base * Power)，但这可以通过添加一个累加器变量作为参数来改变，该变量在每次调用时相乘然后返回您获得的最终累加器。

示例代码:

...
int Power(int base, int exponent, int accumulator)
{
    if (exponent%2==0) 
    { 
        return Power(base*base, exponent/2, accumulator); 
    } 
    else if (exponent%2==1)
    { 
        return Power(base*base, exponent/2, accumulator * base); 
    } 
}
...

其中 Power 最初总是用累加器 1 调用(例如，您可以创建一个替代函数 power(a,b)，如果需要，它只调用 Power(a,b,1))。