Question

某算法的计算时间可用T(n)=2T(n/2)+n表示,求时间复杂度

软考一道题
某算法的计算时间可用T(n)=2T(n/2)+n表示,求该算法时间复杂度
A. O(lgn) B O(nlgn) C O(n) D O(n*n)
答案是B
为什么?
请详细说明原因
谢谢

Answer 1

O（lg2n）其中2是平方。

如果没有给出T(0)的值的话，这du个算法是没有尽头的，虽然可以手算出T(0) = 0，但是专计算机没这属个本事，只会一遍遍的求T(0) = 2 * T(0) + 0 直到堆栈溢出。在加上T(0) = 0这个结束递归的条件之后，这个算法的时间复杂度是O(logN)。

例如：

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

= T(n/2^2) + 2

= T(n/2^3) + 3

= ...

= T(n/2^(log2(n))) + log2(n)

故复杂度是Log2(n)

扩展资料：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

参考资料来源：百度百科-时间复杂性

Answer 2

2T(n/2)也就是说每递归一次，n变为原来的1/2,变为1要递归logn次
后面加个n，每递归一次n减一，需要递归n次
两种递归同步进行，时间复杂度为n*logn
所以答案选b

Answer 3

看清题很关键 题目说的是T(n)是一个算法的计算时间 意思就是T(n)就是这个算法的时间复杂度 把T(n)用数学公式展开 就能得到T(n)=O(nlgn) ~

Answer 4

如图所示。

Answer 5

跟这个差不多吧T(n) = T(n/2) + 1
= T(n/2^2) + 2
= T(n/2^3) + 3
= ...
= T(n/2^(log2(n))) + log2(n)
故复杂度是Log2(n)