> 假设存在O(n)的数组合并算法，那么对任意n个数，将每一个数看成一个只有一个元素的数组，由假设，可以在O(n)时间内将其合并成一个有序数组，即排序问题可以在O(n)时间内解决，这与排序问题的时间下界Ω(nlogn)矛盾，故假设不成立，不存在O(n)的数组合并算法。
> 

• Re:n个数组如何快速合并？ (46) guoxi022 2006-04-24 19:58:14
  • 堆已经足够简单了 (50) xfxyjwf 2006-04-24 20:01:55
  • 你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (50) TN 2006-04-24 20:04:48
    • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (26) guoxi022 2006-04-24 20:11:31
      • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (76) TN 2006-04-24 20:13:50
        • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (88) guoxi022 2006-04-24 20:17:02
          • Re:你是不是理解错了堆的方法了？堆应该是O（NLogK)的吧？而且不是把第一个数组做成堆 (50) guoxi022 2006-04-24 20:18:24