首页 > 试题广场 >

递归公式 的时间复杂度为( &...

[单选题]
递归公式


的时间复杂度为()。
  • O(n)
  • O(logn)
  • O(nlogn)
  • O(n^2)
发表于 2019-11-04 16:30:17 回复(14)
不明觉厉转载答案:https://www.jianshu.com/p/0c2652b4e51f
【master公式的使用】
T(N) = a*T(N/b) + O(N^d)
T(N)是样本量为N的情况下的时间复杂度,a是子过程的部分,N/b是子过程的运行次数,N^d剩余其他的过程。
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)

本题 a=4, b=2, d=1, case 1) O(n^2)
发表于 2019-10-04 18:47:30 回复(4)
我有个问题,就是时间复杂度不是先要求出来执行的次数吗???
为什么推荐解答直接算的f(n)=2n^2-n 就直接得出O(n^2)了,不是要算k=log2n才对吗?
发表于 2020-03-11 15:14:58 回复(3)
垃圾题,图片都显示不出来,盲猜n2
发表于 2019-08-16 17:56:34 回复(0)
题目是啥 ?  完全看不到

发表于 2019-08-16 19:48:14 回复(0)
这个题可以使用代入法来快速求解,n=8时,执行4次,n=4时执行3次,n=2时执行2次,然后对比选项,选到O(logn)
编辑于 2021-11-20 16:37:18 回复(0)
发表于 2021-07-21 09:48:42 回复(0)
T(n)=4T(n/2)+n
=16T(n/8)+n+n
=64T(n/32)+4n+n+n
=4^i * T(2n/(4^i))+(1+4++4^2+...+4^i)n + n
=4^i * T(2n/(4^i))+(4^(n+1) - 1)/3 * n + n
=2n * T(1) + (?)

数学功底不好,这里就推导不下去了,只能猜个n^2
发表于 2019-10-04 18:19:45 回复(1)
题目给的答案是错了吧。。。。
发表于 2023-11-22 18:01:07 回复(0)
???
发表于 2023-06-12 14:32:28 回复(0)
这题我只会master公式,不应该是n方吗?
发表于 2023-02-14 13:08:40 回复(0)
不是可以用递归主定理公式来解吗
发表于 2021-12-18 12:05:23 回复(0)
&amp;<p>不明觉厉转载答案:https://www.jianshu.com/p/0c2652b4e51f 【master公式的使用】 T(N) = a*T(N/b) + O(N^d) T(N)是样本量为N的情况下的时间复杂度,a是子过程的部分,N/b是子过程的运行次数,N^d剩余其他的过程。 1) log(b,a) &gt; d -&gt; 复杂度为O(N^log(b,a)) 2) log(b,a) = d -&gt; 复杂度为O(N^d * logN) 3) log(b,a) &lt; d -&gt; 复杂度为O(N^d) </p><p> 本题 a=4, b=2, d=1, case 1) O(n^2)</p>
发表于 2020-05-12 22:58:35 回复(0)
int T(n){
    if(n==1)return 1;
    return 4*T(n/2)+n;
}

为啥是n^2啊,每次一次调用,没有划分成4个子问题啊
发表于 2019-11-09 20:36:37 回复(0)
a=4 b=2 n^log(b)a=n^2 f(n)=n case1 T(n)=O(n^2)
发表于 2019-09-10 17:20:52 回复(0)