关于adj数组中存放哈希表的空间复杂度疑问
来源：2-8 实现邻接表的改进
软件工程小白菜
2019-08-08
波波老师您好，如果adj数组中每一个元素都是一个哈希表，那么此时每一个哈希表我们可以用一个长度为V-1的数组来表示所有可能相邻的顶点。如果顶点v与另一个顶点w相邻，则我们可以将adj[v][w]设置为1表示true。那么在这种情况下，虽然我们查找两点是否相邻的时间复杂度降到了O(1)级别，但是数据结构本质上变回了一个邻接矩阵，空间复杂度变回了O(V*V)。
而反观红黑树的实现，虽然查找两点相邻的时间复杂度是O(logV)级别，但空间复杂度依旧维持了O(V + E)。
请问波波老师，这样对比下来，是否可以说红黑树的实现会更优于哈希表的实现？还是说其实存在更好的哈希函数能避开哈希表空间复杂度的尴尬呢？
多谢老师！
1回答
-
1）
首先你的分析是对的，课程中也介绍过，使用哈希表是费空间的。当然，这也依赖哈希表的具体实现。但是，红黑树稳稳地是O(V+E)的空间。不过，因为在大多数情况下，现代计算机解决问题，不是特别特殊的情况，对空间都是不敏感的，所以，我们在通常情况下做算法设计，一般都不强调空间。比如在一般的算法比赛中，我没有见过使用哈希表超空间，使用红黑树就ok的情况。
2）
使用哈希表或者红黑树的关键优势还是在于，遍历一个顶点的所有相邻顶点，时间是O(degree(v))级别的操作，而不是O(V)级别的操作。这非常重要，使得很多图论算法的时间复杂度成为了O(V+E)，而不是O(V^2)。
3）
使用红黑树或者哈希表的另一个优点，是能够快速查找某两个节点是否相邻。
但是，后续学习很多具体的图论算法，你就会看到，其实，我们在大多数算法中，都并不需要这个操作。最重要的核心操作，还是遍历一个顶点的所有相邻顶点。因此，邻接表的一个经典实现，还是使用链表：）
继续加油！：）
142019-08-09
相似问题