单项选择题
快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O（n2），而归并排序的时间复杂性为O（nlogn），究其原因，下面的解释哪个正确？（）
A.这是因为归并排序把问题划分为子问题时的时间复杂性是O（1），而快速排序划分为子问题是使用partition（）函数，其时间复杂性是O（n）
B.因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition（）函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T（n）=T（n-1）+O（n）
C.因为快速排序将问题划分为子问题的个数比归并排序要多
D.归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和
点击查看答案
相关考题
-
单项选择题
已知斐波那契数列中第n个斐波那契数F（n）=F（n-1）+F（n-2），问能不能使用分治策略求第n个斐波那契数（）。
A.不能，因为它不可以用分、治、合三个步骤完成计算
B.不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）
C.能，因为它满足分治法的四个适应条件
D.能，因为它可以用分、治、合三个步骤完成计算 -
单项选择题
分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T（n）的一个递归方程，然后解此方程可得T（n）的结果。T（n）的递归定义如下：关于该定义中k，n/m，f（n）的解释准确的是（）。
A.k是常系数，n/m是规模为n的问题分为m个子问题，f（n）是将子问题的解合并为问题的解的时间复杂性
B.k是子问题个数，n/m是子问题的规模，f（n）是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和
C.k是子问题个数，n/m是子问题的规模，f（n）是规模为n的问题分解为子问题的时间复杂性
D.k是常系数；n/m是规模为n的问题分为m个子问题；f（n）是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和 -
单项选择题
分治法解决问题分为三步走，即分、治、合。下面列出了几种操作，请按分、治、合顺序选择正确的表述（）。（1）将各个子问题的解合并为原问题的解（2）将问题分解为各自独立的多个子问题（3）将多个子问题合并为原问题（4）求各个子问题的解（5）将问题分解为可重复的多个子问题
A.（2）（4）（1）
B.（2）（1）（3）
C.（5）（4）（1）
D.（5）（1）（3）
