首页 > 试题广场 >

以下函数的时间复杂度是多少？

[单选题]
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(n^2*m^2)
  • O(2^n)
  • O(n!)
添加回答
推荐
Yano_nankai头像 Yano_nankai
C
这个函数，时间复杂度只与n有关，m和o只是打酱油的。

n会递归两次n-1
n-1会递归两次n-2
n-2会递归两次n-3

所以，是一个完全二叉树，总共是2^n-1次，时间复杂度O(2^n)
编辑于 2016-01-13 11:57:44 回复(3)
xiaoma123头像 xiaoma123
递推公式 
T(n) = 2 * T(n-1)
T(n) = 2 * ( 2 * (T(n-2) ) ) = ... = 2^n * T(1) 
T(1)  = O(1)
T(n) = O(2^n)
发表于 2016-04-18 00:41:17 回复(3)
zgljl2012头像 zgljl2012
从结束条件看，时间复杂度只与n有关，整个程序的执行顺序是一个二叉树，如下：
n
n-1 n-1
n-2 n-2 n-2 n-2
n-3 n-3 n-3 n-3 n-3 ......
......
1 1 1 1 1 1 1......

从n到1，共n层，故所有的计算次数为：1+2+4+...+2^n

等比数列求和知时间复杂度为O(2^n)。

编辑于 2016-01-12 15:08:20 回复(3)
倒悬的橙子头像 倒悬的橙子
发表于 2018-01-08 14:21:29 回复(0)
海洋天堂头像 海洋天堂
咱们不用管后面的m和o，因为循环的判断条件是n，你看if语句里面，是n<=0的时候跳出循环，所以n才是重点，当n>0时，一个recursive(n)需要处理2个recursive(n-1),递归下去，每个recursive(n-1)又要处理2个recursive(n-2),所以这个函数一共要处理2^n个recursive(0,m,o);所以时间复杂度为O(2^n)。
这里，2^n 表示 2的n次方。
发表于 2018-05-24 20:26:20 回复(0)
QuinLan0926头像 QuinLan0926
树的遍历都是o(n)
发表于 2019-03-10 21:09:37 回复(0)
吕希求头像 吕希求
服了,我都点了C了,结果说我空
发表于 2019-01-30 16:28:41 回复(0)
歌浅头像 歌浅
请问recursive(n - 1, m + 1, o);这个函数是什么意思？
发表于 2017-02-16 10:21:51 回复(1)
细雨湿身头像 细雨湿身
这个函数，时间复杂度只与n有关，m和o只是打酱油的。

n会递归两次n-1
n-1会递归两次n-2
n-2会递归两次n-3

所以，是一个完全二叉树，总共是2^n-1次，时间复杂度O(2^n)
发表于 2016-09-15 20:54:52 回复(0)
ABCD头像 ABCD
时间复杂度是怎么计算的？
发表于 2015-06-08 15:10:37 回复(0)
大胞头像 大胞
这个答案应该是C。自己画一下递归树就可以理解了
发表于 2015-05-04 19:57:35 回复(0)
小海豹头像 小海豹
这个应该是A吧
发表于 2014-12-29 01:27:05 回复(2)
提交观点

问题信息

复杂度 京东 C++
上传者：飞鱼
难度：
12条回答 12940浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号