[问题] tree isomorphism 时间复杂度分析 powertodream PTT批踢踢实业坊

[问题] tree isomorphism 时间复杂度分析

楼主: powertodream (The Beginning) 2018-01-10 16:40:53

https://www.geeksforgeeks.org/tree-isomorphism-problem/
两个树是isomorphism, 如果透过swap left/right child可以一样
用dfs 递回可以解决.
但时间复杂度, 看这篇文章是说O(m+n)
我怎么想都至少是指数的时间复杂度以上?
请问大家知道怎么分析吗?
谢谢.

作者: springman (司布林) 2018-01-13 10:14:00

我也认为是 exponential time。

作者: oToToT (å±å©) 2018-01-15 20:00:00

懒的话实际跑一下就感觉的出来了吧(?

继续阅读

Re: [问题] 解最小平方法的问题 Ax~bj0958322080 [请益] 寻找数学软件paddyzb Re: [问题] 解最小平方法的问题 Ax~bLeon Re: [问题] 解最小平方法的问题 Ax~bDJWS Fw: [问题] 解最小平方法的问题 Ax~bj0958322080 [情报] g0v 公民科技创新奖助金 1.1 开放提案monos Re: [问题] 绳子围石头iago2007 [问题] LeetCode 最长回文子字串ken1325 Re: [问题] 绳子围石头cocoyan [问题]几个关于资料结构的疑问smilesaline