软考一道题
某算法的计算时间可用T(n)=2T(n/2)+n表示,求该算法时间复杂度
A. O(lgn) B O(nlgn) C O(n) D O(n*n)
答案是B
为什么?
请详细说明原因
谢谢
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)。
参考资料来源:百度百科-时间复杂性