[問題] tree isomorphism 時間複雜度分析
看板Prob_Solve (計算數學 Problem Solving)作者powertodream (The Beginning)時間6年前 (2018/01/10 16:40)推噓2(2推 0噓 0→)留言2則, 2人參與討論串1/1
https://www.geeksforgeeks.org/tree-isomorphism-problem/
兩個樹是isomorphism, 如果透過swap left/right child可以一樣
用dfs 遞迴可以解決.
但時間複雜度, 看這篇文章是說O(m+n)
我怎麼想都至少是指數的時間複雜度以上?
請問大家知道怎麼分析嗎?
謝謝.
--
人類從歷史得到的教訓就是人類不曾從歷史得到教訓
(黑格爾).
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.152.192
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1515573657.A.B9E.html
推
01/13 10:14,
6年前
, 1F
01/13 10:14, 1F
推
01/15 20:00,
6年前
, 2F
01/15 20:00, 2F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
