2020-2021:teams:legal_string:jxm2001:树同构
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/15 16:31] jxm2001 |
2020-2021:teams:legal_string:jxm2001:树同构 [2020/08/16 11:05] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 133: | 行 133: | ||
| 上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。 | 上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。 | ||
| - | 发现可以用名次代替括号序列。考虑根据深度化为树，每个深度为 $d$ 的结点的名次序列由深度为 $d+1$ 的结点的名次构成。 | + | 发现可以用名次代替括号序列。考虑根据对所有同一深度的树排序，每个深度为 $d$ 的结点的序列由深度为 $d+1$ 的儿子结点的名次构成。 |
| 注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。 | 注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。 | ||
| - | 然后对所有深度为 $d$ 的结点的名次序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。 | + | 然后对所有深度为 $d$ 的结点的序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。<del>但是树哈希太香了</del> |
| ===== 算法练习 ===== | ===== 算法练习 ===== | ||
2020-2021/teams/legal_string/jxm2001/树同构.1597480296.txt.gz · 最后更改: 2020/08/15 16:31 由 jxm2001
