psi*_*lia 6 algorithm math big-o graph data-structures
上图是什么样的问题是速度更快(在大O方面)利用关联矩阵的数据结构,而不是更广泛的邻接矩阵解决？
结构的空间复杂性是:
邻接:O(V ^ 2)发生率:O(VE)
结果是,如果有比边更多的顶点,则入射结构可以节省空间.
您可以查看一些典型图形操作的时间复杂度:
找到与顶点相邻的所有顶点:Adj:O(V)Inc:O(VE)
检查两个顶点是否相邻:Adj:O(1)Inc:O(E)
计算顶点的化合价:Adj:O(V)Inc:O(E)
等等.对于任何给定的算法,您可以使用上述构建块来计算哪种表示为您提供更好的总体时间复杂度.
最后要注意的是,除了最密集的图形之外,使用任何类型的矩阵对于除了最密集的图形以外的所有图形都是极其空间效率的.我建议不要使用其中任何一个,除非您有意识地驳回了邻接列表等替代方案.