[問題] 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