Q: DFS / BFS 是否为linear time的算法 ?
碍于图的input较为繁琐 , 大部分的算法复杂度都会以 |V| , |E|去计量
教科书的资料此两算法的复杂度皆为 O (|V|+|E|) ,
部分考古题解答有这种的写法
|E| ≦ |V|^2 ..... 如果是simple graph , node数的平方 可视为是 edge的bound
依照这样的说法 , O (|V|+|E|)这样的复杂度
= O (|V|+|V|^2)
= O (|V|^2)
反来以 edge的角度来呈现复杂度不就变成 O (|E|) = linear !?
以我目前做考题与对观念的了解，图论算法的复杂度为求精确，通会要把每
个项目写清楚，但我上面这样的陈述，我找不到一个好的理由反驳自己，但在结果
上就影响了一个方法是否在linear time能解决，请问我上面这样的说法合乎逻辑吗?