单选题
适中
#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)。