宋人头亚 2022-03-20 22:06 采纳率: 66.7%
浏览 119
已结题

图的广度优先遍历的时间复杂度为什么不是O(max{n,e})呢(语言-c++)

时间复杂度是由一个算法中执行次数最多的语句来确定的吧，那么图的以邻接表为存储形式的广度优先遍历应该由哪个语句才能得出时间复杂度为o(n+e)呢？(我可以理解他遍历了所有顶点和边，但是它每遍历一个顶点的同时也遍历了一条边，所以我觉得应该取n和e的最大值，而不是他们相加)

img

img

  • 写回答

1条回答 默认 最新

  • bostonAlen 2022-03-22 16:08
    关注

    n是图的顶点个数，e代表邻接表表示法边的个数。很容易认为n和指数没有关系，其实还真有关系，指数的个数就是顶点个数，查找每个顶点需要查找的边的个数的总和就是e，时间复杂度一分不差就是o(n+e).

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

问题事件

  • 系统已结题 4月4日
  • 已采纳回答 3月27日
  • 创建了问题 3月20日

悬赏问题

  • ¥15 微信会员卡等级和折扣规则
  • ¥15 微信公众平台自制会员卡可以通过收款码收款码收款进行自动积分吗
  • ¥15 随身WiFi网络灯亮但是没有网络，如何解决？
  • ¥15 gdf格式的脑电数据如何处理matlab
  • ¥20 重新写的代码替换了之后运行hbuliderx就这样了
  • ¥100 监控抖音用户作品更新可以微信公众号提醒
  • ¥15 UE5 如何可以不渲染HDRIBackdrop背景
  • ¥70 2048小游戏毕设项目
  • ¥20 mysql架构，按照姓名分表
  • ¥15 MATLAB实现区间[a,b]上的Gauss-Legendre积分