时间戳

首页 > 解决方案 > 为什么这个函数的时间复杂度不是 O(m!)？

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);
}

标签： cfunctiontime-complexitybig-ocomplexity-theory

解决方案

函数递减n并再次调用自身，因此函数f有N次调用，具有复杂性，所以. 您的错误是将m f(n-1,m-1)* 视为函数F的M调用。O(1)NO(1)=O(N)

推荐阅读