求问个时间复杂度的问题。

K个机器咋一起排啊。。。

分成K份给不同的机器排，然后再归并 【 在 kuangfengwin 的大作中提到: 】 : K个机器咋一起排啊。。。

不太懂。，是O（nlogn）吗？我以为是只是对数底换了，依然是nlogn 。 他们说是nlogk ？ N/klog n/k

假设各机器上排序算法的复杂度是O(nlogn),且忽略机器间数据传输的时间。算法复杂度为O(n/k log(n/k) + n) 通过『我邮2.0』发布

一会我回来宿舍，详细指点为什么是这个复杂度。 【 在 xuzhenqi 的大作中提到: 】 : 假设各机器上排序算法的复杂度是O(nlogn),且忽略机器间数据传输的时间。算法复杂度为O(n/k log(n/k) + n) : 通过『我邮2.0』发布

所以归并起来的时间是n，而不管是几台机器一起归并的？ 【 在 xuzhenqi 的大作中提到: 】 : 假设各机器上排序算法的复杂度是O(nlogn),且忽略机器间数据传输的时间。算法复杂度为O(n/k log(n/k) + n) : : 通过 : ......... [url=http://guiyou.wangx.in]发自「贵邮」

【 在 xuzhenqi 的大作中提到: 】 : 假设各机器上排序算法的复杂度是O(nlogn),且忽略机器间数据传输的时间。算法复杂度为O(n/k log(n/k) + n) : 通过『我邮2.0』发布 你合并的时候是O(1) * n的？？？ how。。 你就算用上个堆也是O(logk) * n 啊。。。

目测是这样的 【 在 heboy22 的大作中提到: 】 : 所以归并起来的时间是n，而不管是几台机器一起归并的？ : : 发自「贵邮」

题目要求是在K台机器上做，因此可以考虑多台机器的并行化。我是这样做的： 首先，各台机器上各自排序，假设各台机器上排序的复杂度为O(nlogn)，每台机器上的数据数量为n/k,则时间复杂读为O(n/k log(n/k) ). 然后进行k台机器的二路归并。 第1次归并，是k台机器中每台机器上有n/k的数据两两归并，考虑并行化，时间复杂度为 2n/k. 第2次归并，是k/2台机器中每台机器上有2n/k的数据两两归并，考虑并行化，时间复杂度为 4n/k. ... 第logk次归并，是2台机器中每台机器上有n/2的数据两两归并，考虑并行化，时间复杂度为 n. (假设k是二次幂) 则这部分的时间复杂读为n/k(2+4+...+k) = 2n - 2n/k. (等比数列求和) 两部分加起来是O(n/k log(n/k) + n - n/k) = O(n/k log(n/k) + n). 这里主要考虑了多台机器并行计算，忽略了数据传输以及同步的时间。 可能会有更好的方法。 【 在 colorest 的大作中提到: 】 : : 你合并的时候是O(1) * n的？？？ how。。 : 你就算用上个堆也是O(logk) * n 啊。。。