宋人头亚 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日

悬赏问题

  • ¥20 Cotex M3的调试和程序执行方式是什么样的？
  • ¥20 java项目连接sqlserver时报ssl相关错误
  • ¥15 一道python难题3
  • ¥15 用matlab 设计一个不动点迭代法求解非线性方程组的代码
  • ¥15 牛顿斯科特系数表表示
  • ¥15 arduino 步进电机
  • ¥20 程序进入HardFault_Handler
  • ¥15 oracle集群安装出bug
  • ¥15 关于#python#的问题：自动化测试
  • ¥20 问题请教！vue项目关于Nginx配置nonce安全策略的问题