原则:空间换时间

很多算法计算方面的优化是通过将过去的计算结果保存来实现的。计算图的最小生成树的Prim算法使用了一个优先队列来存储没有访问过的节点,来计算其和初始节点s之间的最短距离。作为算法中的关键一环,必须要判断出一个给定节点是否已经访问过。因为二叉堆实现的优先队列无法解决这个问题,通过一个单独的布尔数组inQueue来保存每个节点的访问状态。同样在这个算法中,一个重复的key数组保存了计算过的距离,以避免在优先队列中的重复查找。这些额外的存储需要耗费O(n)的空间,却能够确保算法的高效实现。在大多数情况下,用上个O(n)的空间无伤大雅。

有时,输入数据本就需要大量的存储空间,比如说第6章提到的稠密图。通过一个二维数组来存储节点信息,而不是简单地采用邻接表存储,可以显著地提高算法性能。另外,你可能注意到了,对于无向图来说,如果我们使用双倍的存储,即是说通过二维数组存储信息,让edgeInfo[i][j]和edgeInfo[j][i]相等,就可以让算法更加简化。现在就不必考虑当i≤j时访问edgeInfo[i][j]了,然而如果算法里只是需要知道边(i,j)是否存在,这样做可能会导致算法的复杂化。

在有些情况下,一个算法在没有大容量存储时是无法完成运算的。以桶排序为例,如果输入呈正态分布,它能够利用O(n)的存储在线性时间内完成排序。即便目前的现代计算机能够提供非常大的内存,你还是应该注意桶排序的内存占用是非常高的。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元