为何Anagram（变位词）解法的时间复杂度是O(n+m)而非O(n)？

嗨，这个问题问得特别到位！我来给你掰扯清楚这里的门道~

首先得肯定你的观察：在你贴的这个具体实现里，时间复杂度确实可以说是O(n)。因为代码开头就先判断了两个字符串长度是否相等，不等直接返回false——这一步是O(1)；只有当两个字符串长度都是n的时候，才会进入循环遍历n次，最后再遍历26个固定长度的数组（这是O(1)的操作），所以整体就是O(n)。

那为啥会有人标注成O(n+m)呢？主要有这几个原因：

• 这是变位词问题的通用复杂度描述：很多变位词的解法并没有提前做长度判断。比如有些解法是先单独统计s的字符频率（O(n)），再单独统计t的字符频率（O(m)），最后对比频率数组。这种情况下不管n和m是否相等，都要遍历两个字符串，时间复杂度就是实打实的O(n+m)。所以大家提到这个问题时，常常用O(n+m)来指代问题本身的典型复杂度。
• 大O符号的宽泛性：O(n+m)其实是这个问题的一个上界复杂度，它表示算法的运行时间不会超过n+m的线性倍数。即使你的优化实现把复杂度降到了O(n)，O(n+m)依然是正确的——因为当n=m时，O(n+m)等价于O(2n)，而大O符号会忽略常数系数，所以O(2n)就是O(n)，这俩在数学上是等价的。
• 描述习惯问题：有时候大家标注复杂度时，会默认用问题的通用场景来描述，而不是针对某个做了特殊优化的实现。可能标注的人没注意到你这个代码里的提前长度判断，就直接用了通用的O(n+m)。

总结一下：你的这个实现确实通过提前判断长度，把实际运行的时间复杂度优化到了O(n)（当两字符串长度相等时），但O(n+m)作为变位词问题的通用复杂度描述，也是完全正确的，二者并不矛盾~

备注：内容来源于stack exchange，提问作者Nabeel GM