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能解決，請問我上面這樣的說法合乎邏輯嗎?