P119. 树 t 是否等于树 s 的子树

#1

https://algocasts.io/episodes/M0G2Q7mz

#2

@Hawstein 站主有试过在OJ上提交两种解法么？引入hash的实际耗时更高（五十多毫秒），纯递归的却在十几毫秒内，可能是什么原因？

#3

@archy.shawn

OJ 上的运行时间不能作为时间复杂度的参考。时间复杂度都是统计意义上的，而 OJ 上的测试用例会有各种各样可能的 bias，不同的数据特点（数据规模大小，数据分布情况） 对不同的算法各有利弊。举个简单的例子，针对小数组的排序，O(n^2) 的插入排序实际运行时间会比 O(n*log(n)) 的快排还要少。

因此，在 OJ 上，一个时间复杂度更小的算法却运行了更长的时间，这是很常见的。不用觉得奇怪。OJ 的测试用例最主要是保证测试的全面性，确保在测试这个算法的正确性时，考虑了所有的 case。这些测试数据并不负责 benchmark 这一块。

1赞