[問題] tree isomorphism 時間複雜度分析

看板Prob_Solve作者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

推

springman

01/13 10:14, 6年前 , 1^F

01/13 10:14, 1^F

推

oToToT

01/15 20:00, 6年前 , 2^F

01/15 20:00, 2^F

‣ 返回看板[ Prob_Solve ] 研討

‣ 更多 powertodream 的文章

文章代碼(AID): #1QLT6PkU (Prob_Solve)