题目内容
（请给出正确答案）
提问人：网友黄平
发布时间：2022-01-06
[单选题]
设n是k的倍数，有k个排好序的数表
设n是k的倍数，有k个排好序的数表
，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是
。使用顺序归并算法，即先归并
和
，接着把得到的数表-与
归并，再把得到的数表-与
归并，…，直到得到-
。 例如
，那么归并过程是：-
-
-
。当
顺序归并成数表-
的过程中在最坏情况下的比较次数记作
，那么
满足递推方程和初值是: 
从下述答案中选择适当的答案填入上面的括号内。
A.
B.
C.
D.
E.
参考答案
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
查看官方参考答案
网友提供的答案
共位网友提供了参考答案，
查看全部
- · 有2位网友选择 C，占比25%
- · 有2位网友选择 B，占比25%
- · 有2位网友选择 E，占比25%
- · 有1位网友选择 D，占比12.5%
- · 有1位网友选择 A，占比12.5%
，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是
。使用二分归并的算法。不妨设k为2的幂。将k个数表两两分组，即归并
-
,
-
, …,
-
，得到k/2个归并好的数表，然后对这些数表再两两分组，继续归并。 例如
，那么归并过程是：
-
-
。 以比较做基本运算，采用这种归并算法，最坏情况下的时间复杂度是(
)。
，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是
。使用顺序归并算法，即先归并
和
，接着把得到的数表
归并，再把得到的数表
归并，…，直到得到
。 例如
，那么归并过程是：
-
-
。 以比较做基本运算，那么顺序归并算法最坏情况下的时间复杂度是（
）。
，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是
。使用二分归并的算法。不妨设k为2的幂。将k个数表两两分组，即归并
-
,
-
, …,
-
，得到k/2个归并好的数表，然后对这些数表再两两分组，继续归并。 例如
，那么归并过程是：
-
-
。 以比较做基本运算，采用这种归并算法，最坏情况下的时间复杂度是(
)。
，那么归并过程是：
-
-
。 以比较做基本运算，那么顺序归并算法最坏情况下的时间复杂度是（
顺序归并成数表
的过程中在最坏情况下的比较次数记作
，那么
满足递推方程和初值是:
从下述答案中选择适当的答案填入上面的括号内。
