网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
数据结构吧 关注：104,513贴子：883,666
  • 4回复贴，共1页

邻接表存储有向量G 求任一顶点度数的时间复杂度 O（e/n）

对于一个具有n个顶点和e条边的有向图G求任一顶点度数的时间复杂度 O（e/n）
为啥是O（e/n） 想不通呀。也有的说n+e的。




更新一下记录贴。是求有向图G第K个顶点的出度。
时间复杂度就在while循环那里，顶点的出度就是它的边表的结点个数，E条边，N个顶点，平均就是E/n


无向图的邻接表，顶点的度就是这个顶点对应的链表的点的个数，平均是就是e/n


感谢分享


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 4回复贴，共1页
分享到: