为何O(n)的字典计数排列校验函数比O(nlogn)的sorted方案实测更慢

矛盾原因解答 #

时间复杂度假设是否有误？ #

你的时间复杂度推导没有错误：is_perm的时间复杂度确实是O(nlogn)，is_perm2的时间复杂度确实是O(n)。出现耗时矛盾和时间复杂度理论本身不冲突，因为时间复杂度描述的是输入规模趋近于无穷大时的执行效率增长趋势，不代表小输入规模下的绝对耗时高低。

具体耗时差异原因 #

• 内置函数的底层实现开销远低于纯Python代码：sorted是Python内置的C语言实现函数，执行过程完全绕过Python字节码解释的额外开销，哪怕逻辑是O(nlogn)，单步操作的耗时比Python层面的操作低1~2个数量级。而你写的is_perm2的所有逻辑（字符遍历、字典存在性判断、数值更新、最终字典对比）都在Python解释器层面执行，每一步都要做类型检查、字节码解析、对象引用计数更新等额外操作，常数项开销极高。
• 测试输入规模太小，复杂度阶数的影响被常数项覆盖：你测试用的字符串仅10个字符，O(nlogn)的操作量约为10*log₂10≈33次，O(n)的操作量约为20次，二者操作量本身差异极小，常数项的影响远大于复杂度阶数的差异，因此出现O(n)代码更慢的情况。如果你将测试字符串长度提升到1000甚至10000以上，就能看到is_perm2的耗时逐渐低于is_perm。
• 现有代码存在可优化空间：你可以在函数开头先判断两个字符串长度是否相等，长度不等直接返回False，能直接避免大量无意义的遍历操作，进一步降低is_perm2的耗时。

内容的提问来源于stack exchange，提问作者Moritz Wolff