我要招人

去企业版

首页 > 试题广场 >

求递归方程T(n)=4T(n2)+n 的解 (

[单选题]

求递归方程T(n)=4T(n/2)+n 的解 ( )

查看正确选项

阿里噶多

T(n)+n=4[T(n/2)+n/2]

发表于 2020-02-06 15:38:57 回复(2)

Yeira

使用定理：https://blog.csdn.net/weixin_43865875/article/details/119283075

发表于 2021-07-31 23:37:12 回复(0)

MapleAndJoker

观察可得T(n)+n=4[T(n/2)+n/2] 令an=Tn+n 得an=4a(n/2) 代入an=n平方等式成立

发表于 2020-02-29 17:44:31 回复(1)

2017网络赛

这个主要是考察了递归的展开，展开完之后要进行求和，之后就是看其最高系数项

发表于 2020-01-31 20:38:03 回复(0)

MALK

不是，这里乘4就递归四次？不是递归一次，计算完n/2然后把他的答案直接*4吗，每次n都减少一半。

如果是f(n/2)+f(n/2)+f(n/2)+f(n/2)才是n^2吧??

发表于 2021-08-19 23:21:57 回复(0)

vicyor

主定理提供了分治方法带来的递归表达式的渐进复杂度分析.

1.将规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d)

即T(n)=a(n/b)+c(n^d)

若 a=b^d , T(n)=O(n^dlog(n))

若 a<b^d , T(n)=O(n^d)

若a>b^d , T(n)=O(n^logb(a))

该题 a=4,b=2,d=1,a>2 T(n)=O(n^logb(a))=O(n^2)

发表于 2020-02-14 22:23:45 回复(1)

百年不死小强

T(n) = 4T(n/2) + n

T(n) + n = 4( T(n/2) + n/2)

令f(n) = T(n) + n,

则上面的等式变为：f(n) = 4f(n/2)

所以，答案为B

发表于 2020-02-16 23:11:23 回复(6)

Summer8918_

发表于 2020-01-22 19:51:27 回复(2)

James6

将规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d)

即T(n)=a(n/b)+c(n^d)

若 a=b^d , T(n)=O(n^dlog(n))

若 a<b^d , T(n)=O(n^d)

若a>b^d , T(n)=O(n^logb(a))

该题 a=4,b=2,d=1,a>2 T(n)=O(n^logb(a))=O(n^2)

发表于 2020-06-08 00:36:37 回复(0)

虚言1

T(n)=4T(n/2)+n

=4(4T(n/2*2)+n/2)+n

=4(4(4T(n/2*2*2)+n/2*2)+n/2)+n

...

由此可推算，T(n) = 4^kT(n/2^k)+n+2n+...+n2^k-1

令n = 2^k，则T(n) = n^2T(1)+2^k(1+2+...+2^k-1)

显而易见1+2+...+2^k-1是个等比数列，则根据等比数列求和公式可得

T(n) = n^2T(1)+2^k(2^k-1)=n^2T(1)+n(n-1)=n^2(T(1)+1)-n

T(1)+1是个常数可忽略，T(n) = n^2-n

由此可见时间复杂度为n^2

发表于 2020-05-25 14:45:41 回复(0)

宇宙第亿骚

大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。

找出对应的abc，直接带入。

编辑于 2022-07-17 15:52:08 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师前端工程师算法工程师爱奇艺测试开发工程师 2020 Java工程师

上传者：小小

难度：

11条回答 495收藏 10291浏览

求递归方程T(n)=4T(n2)+n 的解 (

问题信息

热门推荐

相关试题