单选题 适中
#22014

递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度,该算法的时间复杂度是多少?

递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度,该算法的时间复杂度是多少?

未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析

用主定理或递归树法。递归树中:  

第1层总时间复杂度n2;  

第2层2*(n/2)2=n2/2;  

第3层4*(n/4)2=n2/4;  

……总和为n2*(1+1/2+1/4+…)≤2n2,时间复杂度为O(n2)。