首页 > 试题广场 >

以下函数的时间复杂度是 void recursive(int

[单选题]
以下函数的时间复杂度是
void recursive(int n, int m, int o) {
    if (n <= 0) {
        printf("%d, %d \n", m, o);
    } else {
        recursive(n - 1, m + 1, o);
        recursive(n - 1, m, o + 1);
    }
}

  • O(n*m*o)
  • O(2^n)
  • O(n^2*m^2)
  • O(n!)

快速的排除法,当n=1时,执行了2次。带进去选B。

发表于 2019-09-22 20:47:44 回复(0)
本题n,m,o三个参数中,只有n影响时间复杂度;
recursive内部两个recursive的“n”输入一样,说明两个recursive要么都过了 if 条件,要么都没过;
最后时间复杂度 = 2^0 + 2^1 + 2^2 + 。。。+ 2^(n-1) = 2^(n-1) x 2 - 1 = 2^n - 1 
发表于 2020-05-24 12:14:20 回复(0)
随便一想,就是一个类树结构,那么树结构的复杂度就差不多了
发表于 2022-01-30 03:57:08 回复(0)