一道算法题

richiefang · 发表于2010-12-16 15:56

一道算法题 [复制链接]

问题：有k个按升序(从小到大)排好序的序列A0, A1, A2... A(k-1)，总计有n个元素。试问，有没有一个算法将其归并为一个升序序列？
我们希望算法的时间复杂度，为O(n log(k))。

提示：使用堆排序、快速排序和希尔排序，都可以得到O (n log(n))时间复杂度的算法。

小瑞 · 发表于2010-12-16 16:47

这我为啥连题目都看不懂？

richiefang · 发表于2010-12-16 16:59

这说明你需要补习一下数据结构的知识...
题目哪里看不懂？

gaoxiao · 发表于2010-12-17 09:01

不知道楼主想表达什么意思，是要写算法呢？还是干嘛呢？

murray · 发表于2010-12-17 09:06

这个？？？还没做过算法的呢，呵呵，我想到的方法：
2个元素做冒泡排序生成一个新的元素，再和下一个元素冒泡排序。以此类推

richiefang · 发表于2010-12-17 09:13

原帖由 murray 于 2010-12-17 09:06 发表这个？？？还没做过算法的呢，呵呵，我想到的方法： 2个元素做冒泡排序生成一个新的元素，再和下一个元素冒泡排序。以此类推

冒泡排序时间上不满足要求。它的时间复杂度和总元素数量的平方成正比。

kitutwas · 发表于2010-12-17 10:18

原来我很早就在这个网站注册过呀！只是好久都没上了，今天才发现自己早就有账号了。

ch0721 · 发表于2010-12-17 12:15

归并排序不行吗虽然不是2的整次幂可以构造一下吧

ji_dan · 发表于2010-12-18 14:33

级别低，只做过冒泡排序~:L

jjkwz · 发表于2010-12-18 15:03

软件算法，我不会啊，呜呜呜，数学不好

soso · 发表于2010-12-19 10:13

原帖由 kitutwas 于 2010-12-17 10:18 发表原来我很早就在这个网站注册过呀！只是好久都没上了，今天才发现自己早就有账号了。

呵呵欢迎一下

richiefang · 发表于2010-12-20 18:28

原帖由 soso 于 2010-12-19 10:13 发表呵呵欢迎一下

同欢迎一下！我的参考答案这两天就给出。

soso · 发表于2010-12-21 08:40

大家来再做做头脑体操啊

wanghongyang · 发表于2010-12-22 18:55

现在觉得算法越来月有意思了！~

liuceone

能想到的只有冒泡了知识匮乏~~`:L :L