已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ，其中 n 表示问题的规模，另已知算法 B 的运行时间函数为 T(n)=XT(n/4)+n2 ，其中 n 表示问题的规模。对充分大的 n ，若要算法 B 比算法 A 快，则 X 的最大值为（）。
- A.15
- B.17
- C.63
- D.65
正确答案及解析
正确答案
C
解析
本题需要用到特定形式的递归式分析法：
在本题中，a=8,b=2，故符合（1）的情况。
时间复杂度为：O（n3）。
a=16,b=4
已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ，其中 n 表示问题的规模，另已知算法 B 的运行时间函数为 T(n)=XT(n/4)+n2 ，其中 n 表示问题的规模。对充分大的 n ，若要算法 B 比算法 A 快，则 X 的最大值为（）。
本题需要用到特定形式的递归式分析法：
在本题中，a=8,b=2，故符合（1）的情况。
时间复杂度为：O（n3）。
a=16,b=4
