0

我需要一些帮助来理解分析递归算法。我很快就完成了这个算法，想知道复杂度是多少：

int FunctionExampple( A1, A2, ... An )
{
    product = 1;
    if( n == 2)
    {
        product = multi(A1, A2);
    }
    else 
    {
        product = multi(A1, FunctionExample( A2, A3, ..., An ) );
   }
   return product; 
}

现在假设函数 multi 需要 O(n^1.59) 时间，那么复杂度是多少？它会保持 O(n^1.59) 还是递归调用会使其 O(n^1.59 * n ) 来考虑递归调用的数量？多谢你们。

PS：我只是快速写了这个，语法和所有这些都无关紧要。

4

1 回答 1

1

O(n 1.59 ) 中的参数“n”测量“multi”参数的大小，而不是参数的数量。因此，至关重要的是“multi”的输出大小与其输入大小的关系。例如，如果 'multi' 的结果是其任何参数大小的两倍，则调用 multi(A, multi(B, C)) 其中 A, B, C 的大小为 n 为 O(n 1.59 + (2n ) 1.59 )，然后如果您以这种方式将多个调用链接到 multi ，您将获得指数增长。另一方面，如果 'multi' 返回与其输入大小相同的值，则会得到 O(kn 1.59 )，其中 k 是 FunctionExample 的参数数量，n 是它们的（最大）大小。

所以这取决于'multi'的行为方式。例如，如果它是有限域内的乘法与乘法，将会有很大的不同，因为后者的结果不会从输入中增长，而对于无限整数，结果的大小会增长。

于 2012-06-05T18:23:35.750 回答