计算如下代码的时间复杂度与空间复杂度

您提供的代码是一个使用递归计算阶乘和组合数的示例。让我们分别分析时间和空间复杂度。

#include <stdio.h>

// 计算阶乘的递归函数
int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

// 计算组合数的递归函数
int combination(int n, int m) {
    return factorial(n) / (factorial(m) * factorial(n - m));
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n > 0 && m <= n) {
        int result = combination(n, m);
        printf("%d\n", result);
    }
    return 0;
}

**时间复杂度**：
- `factorial` 函数的时间复杂度是 O(n)，因为它直接递归地乘以 n 个数字，直到到达基本情况。
- `combination` 函数内部调用了 `factorial`，所以它的复杂度也是 O(n) 因为 n 阶乘是递归的主要部分。然而，由于 `factorial` 的计算会被共享，所以实际计算时间比直接看两层递归复杂度要低一些。
- 主函数 `main` 中的循环体里有一个组合数的计算，每次循环都是 O(n)，因为组合数函数是 O(n)。整个循环执行 n 次，所以这部分的复杂度也是 O(n)。

综上所述，总的时间复杂度接近于 O(n)，因为循环和组合计算都是线性的。

**空间复杂度**：
- 在该代码中，虽然有两个递归函数，但它们都不涉及额外的数据结构存储，只有基本的局部变量。`factorial` 递归栈的空间占用取决于递归深度，最坏的情况下是 O(n)，因为最深递归是 n 层。
- 主函数的空间复杂度是常量级别的，因为没有额外数组或其他数据结构随着输入大小增长。

因此，整个程序的空间复杂度是 O(n) 作为递归深度的最大值。