作者powertodream (The Beginning)
看板Prob_Solve
標題[問題] tree isomorphism 時間複雜度分析
時間Wed Jan 10 16:40:53 2018
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: 我也認為是 exponential time。 01/13 10:14
推 oToToT: 懶的話實際跑一下就感覺的出來了吧(? 01/15 20:00