c - 为什么此函数的时间复杂度不是O(m!)？

当我试图找出这个函数的时间复杂度时，我得到了m!。
我所做的是

T(n,m)=m*T(n-1,m-1)=m(m-1)T(n-2,m-2)=....=m!T(1,1)

但是时间复杂度的答案是O(n)。为什么？

void f3 (int n, int m)
{
    if (n <= 1)
        return;
    if (m > 1)
        return m*f3(n-1, m-1);
    f3(n-1, m);
}

最佳答案

递归终止取决于n：if (n <= 1) return;
有两种可能的递归调用：m*f3(n-1, m-1)或f3(n-1, m)。（一个或另一个）
参数n在每次调用后递减。因此，最多会有对函数n的调用。
函数f3的剩余时间复杂度是常数。总的时间复杂度为f3。
我建议您在函数的开头添加一个O(n)语句来打印所有调用。这将帮助你了解正在发生的事情。

关于c - 为什么此函数的时间复杂度不是O(m!)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51937289/