首页 > 试题广场 >

以下函数的时间复杂度是( ) void foo(int n,

[单选题]
以下函数的时间复杂度是( )
void foo(int n, int x, int y) {
    int z = 0;
    if (n <= 0) {
       z = x + y;
    } else {
        foo(n - 1, x + 1, y);
        foo(n - 1, x, y + 1);
    }
}

  • O(2^n)
  • O(n)
  • O(logn)
  • O(n^2)
应该是2^n啊
发表于 2019-10-18 07:57:19 回复(0)
为什么不是T(n)=T(n-1)+T(n-1)=2T(n-1)=...=2^n * T(1)  呢?
发表于 2019-08-28 11:35:46 回复(1)
这个题有问题,没一个是对的,应该是2^n
发表于 2020-10-28 12:00:59 回复(0)
难道不该是2^n?
发表于 2019-08-15 12:56:16 回复(0)
在方法的一次执行中,会递归调用自身两次,方***执行n次结束运算,故2n
发表于 2023-06-25 21:16:31 回复(0)
T(n)=2T(n-1)+O(1) 。。 T(n)=2(2T(n-2)+O(1))+O(1)=4T(n-2)+3O(1)。。T(n)=2(2(2T(n-3)+O(1))+O(1))+O(1)=8T(n-3)+5O(1) 。。 可得T(n)=2^nT(0)+(2^n-1)O(1) 。。所以T(n)=2^nO(1)+(2^n-1)O(1) 所以复杂度为2^n
发表于 2023-06-15 00:38:14 回复(0)
有道题跟这个一模一样答案是2^n ,所以哪里出问题了

发表于 2020-10-09 22:30:08 回复(0)

应该是2^n,答案错了

发表于 2020-03-02 09:41:23 回复(0)