已知算法 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: 63D
A: 15
B: 17
C: 63D
举一反三
- 已知算法A的运行时间函数为T()=8T(n/2)+n2,其中n 表示问题的规模。另已知算法B的运行时间函数为 T()=XT(n/4)+n2。对充分大的n,若要算法B比算法A快,则X的最大值为()。 A: 15 B: 17 C: 63 D: 65
- 已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为__________(63)。 (63) A: 15 B: 17 C: 63 D: 65
- 已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为__________(63)。 (62) A: Θ(n) B: Θ(nlgn) C: Θ(n2) D: Θ(n3)
- 设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为______ 。
- 设问题规模为N时,某递归算法的时间复杂度记为T(),已知T(1)=1,T()=2T(N/2)+N/2,用O表示的时间复杂度为()。 A: O(logN) B: O(N) C: O(NlogN) D: O(N²logN)