找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: daisy8867
收起左侧

[面经题目讨论] 任意两棵树的最大公共子结构

[复制链接]

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
 楼主| 发表于 10-6-2015 06:07 AM | 显示全部楼层
uuuouou 发表于 10-5-2015 11:02 AM6 Q& A/ [" a) Z+ E3 c& g
感觉可以用分治法来解决,复杂度最坏是O(M*N*min(M, N))的:) I8 u! r" U; \" M! m

$ b& p. |& b5 W# g) @上面代码得到的是最大相同结构的节点集合, ...

& ~9 M2 \! k; s, }! Y; G# L! m4 h没有O(M + N)的办法吗,总觉得可以序列化后找最大公共子序列

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-6-2015 06:38 AM | 显示全部楼层
daisy8867 发表于 10-6-2015 06:07 AM
6 H! q) D! \! |5 J" k  K, F没有O(M + N)的办法吗,总觉得可以序列化后找最大公共子序列
1 s( Z$ C& V4 a# H- q
最长公共子序列的复杂度是O(M * N)呀,O(M + N)的想不出呢
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表