有如下递归函数[1]fact(n),分析其时间复杂度。写出推导过程。int fact(int n){ if(n<=1) return 1; else return n*fact(n-1);}

为了分析该递归函数 fact(n) 的时间复杂度，我们需要先确定其基本操作的执行次数与输入规模 $n$ 之间的关系。

1. 确定基本操作：
   在函数 fact 中，基本操作包括条件判断 if(n<=1) 和乘法运算 n*fact(n-1)（以及函数调用本身的开销）。我们可以假设执行一次基本操作（如判断、乘法、返回）的时间是常数，记为 $O(1)$。

2. 建立时间复杂度的递推关系：
   设 $T(n)$ 为函数 fact(n) 执行所需的时间（即时间复杂度函数）。

   • 当 $n \le 1$ 时，函数直接执行 if 判断并返回 $1$。这属于常数时间操作，即 $T(1) = O(1)$。
   • 当 $n > 1$ 时，函数执行 if 判断（耗时 $O(1)$），然后执行 else 分支。在 else 分支中，它进行一次乘法运算 n * ...（耗时 $O(1)$），并递归调用 fact(n-1)（耗时 $T(n-1)$）。
     因此，我们可以写出递推方程：
     $T(n) = T(n-1) + O(1)$

3. 求解递推关系：
   为了更直观地推导，我们假设 $O(1)$ 为一个常数 $c$。
   $T(n) = T(n-1) + c$
   我们可以通过展开递推式来寻找规律：
   $T(n) = T(n-1) + c$
   $T(n) = [T(n-2) + c] + c = T(n-2) + 2c$
   $T(n) = [T(n-3) + c] + 2c = T(n-3) + 3c$
   以此类推，经过 $k$ 次展开后：
   $T(n) = T(n-k) + k \cdot c$
   当递归到达基本情况时，即 $n-k = 1$，此时 $k = n-1$。代入上式：
   $T(n) = T(1) + (n-1) \cdot c$
   已知 $T(1) = c$ （常数时间），代入得：
   $T(n) = c + (n-1) \cdot c = c + n \cdot c - c = n \cdot c$

4. 得出时间复杂度：
   由于 $T(n) = n \cdot c$，其中 $c$ 是常数，忽略常数因子后，$T(n)$ 与 $n$ 成正比。

该递归函数 fact(n) 的时间复杂度为 $O(n)$。