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

https://algocasts.io/episodes/M0G2Q7mz

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

@archy.shawn

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

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

1赞