首页 > 试题广场 >

请问下面这个函数的时间复杂度是多少(假设 )? func

[不定项选择题]

请问下面这个函数的时间复杂度是多少(假设 )?

function fn(n)
{
   if (n === 1)
     return 1;
   else
     return fn(n-1) + fn(n-1);
}

要是变成2*fn(n-1)就是O(n)的时间复杂度了。
发表于 2018-12-17 18:49:17 回复(0)
这里值得注意的是,里面有两个递归,是先执行第一个递归再执行后一个,故过程就是遍历这个树,复杂度为2^n
发表于 2021-04-04 14:54:13 回复(0)
怎么算的?

发表于 2019-09-03 17:47:33 回复(0)