c - 多次递归调用的时间复杂度是多少？

Question

谁能解释一下我们如何评估这个函数的时间复杂度？

int f(int n) 
{ 
    int x,y,z,t; 
    if(n ==1 || n==0) return n; 
    x=f(n/2); 
    y=f(n/3); 
    z=f(n/4); 
    t=x+y+z; 
    if(t<n) return n; 
    return t; 
}

Answer 1

对于像这样的非显而易见的算法，我总是喜欢对复杂性进行实际测量。您可以像这样修改您的代码:

size_t Counter = 0;

int f(int n) 
{ 
    ++Counter;
    ...

然后做一个简单的测试:

 for (int i = 0; i < 10000; ++i)
 {
     Counter = 0;
     int Result = f(i);
     printf("%d: f(%d) = %d\n", Counter, i, Result);
 }

图表是可视化数据的好方法。对于 0-10000 的 n 函数，我们得到(蓝线是循环计数，红色是线性拟合):

这是一个明显的线性关系。关于此方法的一些重要注意事项:

• 在对较大的 N 进行外推时要小心。对于复杂的算法，行为可能会发生变化，即对于较小的 N，它可能看起来是线性的，但对于较大的 N 会变成二次方(反之亦然)。如果您对 N 的所有值都需要它，那么唯一的方法就是其他答案给出的理论方法。
• 在这种情况下，我测量了循环次数，但在某些情况下，实际测量函数调用时间作为 N 的函数可能会更好。在这种情况下，函数调用时间非常短，并且不会给出结果有意义或易于解释(至少在 0-10000 范围内)。