gemini王者荣耀:9.6 希尔排序
9.6 希尔排序
给大家出一道智力题。请问“VII”是什么?
嗯,很好,它是罗马数字的7。现在我们要给它加上一笔,让它变成8(VIII),应该是非常简单,只需要在右侧加一竖线即可。
现在我请大家试着对罗马数字9,也就是“IX”增加一笔,把它变成6,应该怎么做?
(几分钟后)
我已经听不少声音说,“这怎么可能!”
可为什么一定要用常规方法呢?我这里有3种另类的方法可以实现它。
方法一:观察发现“X”其实可以看作是一个正放一个倒置两个“V”。因此我们,给“IX”中间加一条水平线,上下颠倒,然后遮住下面部分,也就是说,我们所谓的加上一笔就是遮住一部分,于是就得到“VI”,如图9‐6‐1所示。
智力题的答案介绍完了1。大家会发现,看似解决不了的问题,还真不一定就没有办法,也许只是暂时没想到罢了。
我们都能理解,优秀排序算法的首要条件就是速度2。于是人们想了许许多多的办法,目的就是为了提高排序的速度。而在很长的时间里,众人发现尽管各种排序算法花样繁多(比如前面我们提到的三种不同的排序算法),但时间复杂度都是O(n2),似乎没法超越了3。此时,计算机学术界充斥着“排序算法不可能突破O(n2)”的声音。就像刚才大家做智力题的感觉一样,“不可能”成了主流。
终于有一天,当一位科学家发布超越了O(n2)新排序算法后,紧接着就出现了好几种可以超越O(n2)的排序算法,并把内排序算法的时间复杂度提升到了O(nlogn)。“不可能超越O(n2)”彻底成为了历史。
从这里也告诉我们,做任何事,你解决不了时,想一想“Nothing is impossible!”,虽然有点唯心,但这样的思维方式会让你更加深入地思考解决方案,而不是匆忙的放弃。
注:1本智力题摘自《在脑袋一侧猛敲一下》。
注:2还有其他要求,速度是第一位。
注意:3这里排序是指内排序。