非常简单的递归函数复杂度分析

Question

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

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：我只是很快写好了，语法和所有这些东西都无关紧要。

Answer 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（k n^1.59），其中k是FunctionExample的参数数，n是它们的（最大）大小。

所以这取决于"多"的行为方式。 例如，如果是有限域内的乘法与乘法，则会有很大的区别，对于后者，结果不会从输入中增长，而对于无限整数，结果的大小会增加。