原则:选择正确的数据结构

著名算法设计者Robert Tarjan曾经引用过这样一句话:“如果使用正确的数据结构,任何问题都能够在O(n log n)的时间内解决掉”。许多算法需要使用有限队列来存储中间过程或者下一步运算。实现优先队列最常见的要数二叉堆了,它能够在O(log n)的时间内从优先队列中将最低优先级的元素移除。然而,优先堆却不能判定是否包含某个元素。我们在谈到线段扫描(第9章)时提到了这一点,这个算法可以达到O(n log n)的性能,因为其使用了增广二叉树来实现优先队列,并且在移除最小元素时,还能够达到O(log n)的性能。这个原则也可以从反面来理解,如果选择了不恰当的数据结构,那么算法就很难发挥出它最大的威力。

阅读 ‧ 电子书库
阅读 ‧ 电子书库