求助几道算法问题
有些符号打不出来，留下邮箱详谈
2.考虑用以下算法排序N个元素：把每个元素放入自己的列表中。然后反复执行下面的步骤N-1次：选择2个表，然后合并他们。注意每次合并把列表数量减少到1，但是保留了排好序的所有列表。所有到了最后，留下的就是一个由N个元素排好序列的表。
A．假设初始N列表放在了一个栈上，然后在任何时候，都是前2个列表被选中合并，结果被放在栈顶，那这个排序算法的运行时间是多少？
B．假设初始N列表放在队列中。爱人和时候，都是前2个列表被选中合并，结果被放在队列最后，那这个排序算法的运行时间是多少？
3.假设我们想要分配N个物品为G个相等大小的群，大小N/G。最小的N/G物品在1群里面，第二小的N/G物品哎2群，以此类推。群本身不需要排序。为了简单，你可以假设N和G是2的乘方，给出一个O(N log G)算法解出这个问题。
4.假设 K 是一个大于等于2的常数。
证明合并由N个数组成的K个已排序数组需要至少K N-1次比较。或者提供一个用了少于KN-1次比较的算法证明这个声明是错的。
[解决办法]
2. 这个要倒过来看.
①T(n) = T(n - 1) + O(n)
②T(n) = 2T(n / 2) + O(n)
3. 我的想法是首先选出G个群的首元素, 使用类快排方式获取序号元素(算法复杂度为(lgN)), 则此步骤为G*lgN.
剩下的就是使用二分查找确定其具体属于哪个群, 算法为N * lgG.
综合: G*lgN + N*lgG.
而G*lgN = O(N*lgG) 当G=O(N)时.
4. 错误. 事实上有O(N*lgK)的算法.
算法的核心在于如果从K个数组中的首元素中选取最小的一个, 一般方法需要k - 1次比较找出最小值. 如果使用堆来管理最小的K个元素, 则每次取出最小的只需一次, 然后将最小的下一个添加进堆中, 需要lgK次. 综述:
约为N*lgK.
