设某算法的计算时间可用递推关系式T(n)=2T(n／2)n表示，则该算法的时间复杂度为( )。

admin2019-06-12 22

问题设某算法的计算时间可用递推关系式T(n)=2T(n／2)n表示，则该算法的时间复杂度为( )。

选项 A、O(lgn)
B、O(nlgn)
C、O(n)
D、O(n²)

答案B

解析递推关系式T(n)=2T(n／2)n其实是在给n个元素进行快速排序时最好情况(每次分割都恰好将记录分为两个长度相等的子序列)下的时间递推关系式，其中T(n／2)是一个子表需要的处理时间，n为当次分割需要的时间。注意，这里实际上是用比较次数来度
量时间。可以对此表达式进行变形得

用n／2代替上式中的n可得

继续用n／2代替上式中的n可得

算法共需要进行[1bn]+1次分割(n个元素的序列的对半分割树的高度跟具有n个结点的完全二叉树高度相等，软设级别的只需知道即可，不必深究)，将上述[1bn]+1个式子相加，删除相互抵消的部分得

而T(1)=1，那么上式可转化为
T(n)=n[1bn]+2n
而在求时间复杂度时关注“大头”，注意到O(n)T(n)=O(nlogn)=O(nlgn)
数学上，一般将底为10的对数简略写成lgn。

转载请注明原文地址:https://kaotiyun.com/show/0ECZ777K

软件设计师上午基础知识考试

相关试题推荐

随机试题

最新回复(0)