作者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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1515573657.A.B9E.html
1F：推 springman: 我也认为是 exponential time。 01/13 10:14
2F：推 oToToT: 懒的话实际跑一下就感觉的出来了吧(? 01/15 20:00