OJ 上为什么时间复杂度更优的算法却运行了更长时间

原问题

由于这是一个一般化的问题,因此把回答单独抽出来,放在「问答」这个分类下,方便查看。

回答

OJ 上的运行时间不能作为时间复杂度的参考 。时间复杂度都是统计意义上的,而 OJ 上的测试用例会有各种各样可能的 bias,不同的数据特点(数据规模大小,数据分布情况) 对不同的算法各有利弊。举个简单的例子,针对小数组的排序,O(n^2) 的插入排序实际运行时间会比 O(n*log(n)) 的快排还要少。另外还有一点,某些时间复杂度更优的算法由于引入了更复杂的数据结构,会带来一些额外的时间开销, 当测试数据规模太小时 ,更优算法所带来的时间收益有可能小于复杂数据结构所引入的时间开销,这时也可能会发现一个时间复杂度更优的算法实际却运行了更多的时间。

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

1赞