首页 > 试题广场 >

T(n) = 25T(n5)+n^2的时间复杂度？

[单选题]
如果一个算法的时间复杂度T(n)的可以表示为，则T(n) = ? 
  • O((n^2)*(lgn))
  • O(n^2)
  • O(logn)
  • O(n^3)
添加回答
推荐
ClumsyBird头像 ClumsyBird
A.
T(n) = 25*T(n/5) + n^2
       = 25*( 25*T(n/25) + (n/5)2 ) + n^2 
       = 5^4*T(n/52) + 2*n^2 
       = 5^(2k)*T(n/5k) + k*n^2 
根据主方法，有T(n) = aT(n/b)+O(n^d), 则a=5^(2k), b=5k, d=2, a=b^d。
所以T(n)=O(n^d*(lgn))=O(n^2(lgn)).
编辑于 2015-04-07 16:27:26 回复(3)
你_不要_说话头像 你_不要_说话

T(n) = 25T(n/5)+n^2 = 25(25T(n/25)+n^2/25)+n^2
= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= ....
= 25 ^ x * T( n / 5^x ) + x * n^2


T(n) = 25T(n/5)+n^2
T(0) = 25T(0) + n^2 ==> T(0) = 0
T(1) = 25T(0)+n^2 ==> T(1) = 1


x = lg 5 n
25 ^ x * T( n / 5^x ) + x * n^2
= n^2 * 1 + lg 5 n * n^2
= n^2*(lgn)

发表于 2016-08-28 20:13:22 回复(5)
美团到店招聘头像 美团到店招聘
主方法公式套一套
发表于 2017-03-03 16:41:51 回复(0)
孙强Jimmy头像 孙强Jimmy
根据题设，a = 25, b = 5, d = 2，则d = logba，所以时间复杂度为O(ndlgn) = O(n^2*(lgn))
发表于 2017-07-27 09:26:34 回复(2)
igigmn头像 igigmn
T(n)=a*T(n/b)+c*n^k
if a=b^k  
then T(n)=O( n^k *log(n) )
编辑于 2015-03-03 22:02:37 回复(0)
最爱可乐头像 最爱可乐
《算法导论》主方法求解递归式，T(n) = aT(n/b) + f(n),如果f(n)=O(nlog b a),则T(n)=O(n log b algn) 
发表于 2015-06-14 11:51:04 回复(1)
fengqiusuo头像 fengqiusuo
选A  不过通过从网上查资料，觉得正确答案应该是：O(n^2*log5(n))，其中log5(n)表示以5为底n的对数。
继续翻《算法导论》，并请教实验室师兄，认为n趋近于无穷大时，log5(n)与lg n 等价，所以O(n^2*log5(n)) = O(n^2*lg n )。
至此，终于算是弄明白了。希望能跟大家一起讨论，学习。
编辑于 2016-07-01 17:14:30 回复(0)
天上白云蓝湛湛～头像 天上白云蓝湛湛～
A
T(n) = 25*T(n/5) + n^2
       = 25*( 25*T(n/25) + (n/5)2 ) + n^2 
       = 5^4*T(n/52) + 2*n^2 
       = 5^(2k)*T(n/5k) + k*n^2 
       = 5^(2log 5 n)*T(1) + (log 5 n)*n^2 
       = n^2*1 + (log 5 n)*n^2
发表于 2019-08-01 17:19:26 回复(0)
TTT爱吃糖头像 TTT爱吃糖
码，
发表于 2018-10-11 16:44:03 回复(0)
RedGrey1993头像 RedGrey1993
按答案来看他这道题后面的n^2少了个大O符号。
发表于 2020-04-23 00:52:56 回复(0)
张博16头像 张博16
奇怪的题目, n平方复杂度不应该是O1么.乘法跟n有什么关系.
发表于 2020-04-12 15:11:18 回复(0)
🍉Mr.Lew头像 🍉Mr.Lew
还可以画出递归树，树深度*每层时间复杂度
发表于 2019-10-24 15:58:16 回复(0)
BernardLowe头像 BernardLowe
T(n)=25T(n/5)+n^2中由主方法得a=25,b=5,f(n)=n^2 因此n^logb(a)=nlog5(25)=n^2=f(n) 故满足主方法2个，所以 T(n)=O(nlogb(a)lgn)=O(n^2lgn) 算法导论第三版中文 54页
编辑于 2016-11-11 20:00:00 回复(0)
辉88头像 辉88
T（n） = n^2 + k^2*T(n/k)
            = n^2 + k^2*(n^2/k^2+k^2*T(n/k^2))
            = n^2 + n^2 + k^4*T(n/k^2)
            所以此时可以之后后面大约会有logkn
发表于 2016-09-22 14:20:48 回复(0)
想打架的蜜蜂头像 想打架的蜜蜂
算法导论主定理
发表于 2015-08-31 21:30:38 回复(0)
借夕头像 借夕
为什么是A，不懂！！！
发表于 2015-04-07 16:10:11 回复(1)
有收我就去头像 有收我就去
T(n) = 25*T(n/5) + n2
          = 25*( 25*T(n/25) + (n/5)2 ) + n2
       = 54 T(n/52) + 2*n2
        = 52kT(n/5k) + k*n2
 即   n2+k*n2，又 n == 5k，所以大概是A
编辑于 2015-04-07 16:23:03 回复(0)
zxcqwe头像 zxcqwe
a
发表于 2015-01-03 15:25:32 回复(0)
yanglichun头像 yanglichun
选C
每次迭代除以5
发表于 2015-01-03 13:51:14 回复(0)
提交观点

问题信息

谷歌 复杂度
来自：算法工程师能力评估
上传者：小海豹
难度：
19条回答 25948浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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