字符串拆分排序的时间复杂度及排列校验算法的复杂度计算

你给出的这个判断两个字符串是否互为排列的函数，最坏时间复杂度为O(n log n)，其中n为输入字符串的长度，你的推导思路完全正确。

逐步骤复杂度拆解 #

我们默认分析两个字符串长度相等的最坏情况（长度不等时直接返回，复杂度为O(1)），对每一步操作的耗时拆解如下：

• 字符串转数组的split('')操作：需要遍历每个字符存入数组，时间复杂度O(n)
• 内置sort排序操作：目前主流JS引擎（如Chrome V8、Node.js）的Array.sort均采用Timsort算法实现，平均和最坏时间复杂度均为O(n log n)。这里简单解释下这个复杂度的由来：所有基于元素两两比较的排序算法，理论时间下界就是Ω(n log n)，工业界实现的内置排序都是在这个下界基础上做的工程优化，所以不会突破这个复杂度量级。
• 数组转回字符串的join('')操作：需要遍历数组每个字符拼接为字符串，时间复杂度O(n)
• 最后两个排序后字符串的全等比较：需要逐字符对比校验，时间复杂度O(n)

低阶操作耗时可忽略的原因 #

大O时间复杂度的核心定义是描述输入规模n趋近于无穷大时，算法耗时的增长趋势，计算时只会保留增长速度最快的最高阶项，低阶项和常数系数都会直接忽略。
在这个场景下，所有非排序操作的总复杂度为O(n)，比排序的O(n log n)增长速度慢得多，当n足够大时，O(n)的耗时和O(n log n)相比几乎可以忽略不计，所以整体复杂度直接取最高阶的O(n log n)即可。

补充优化思路 #

如果题目限定了字符集范围（比如仅小写英文字母、ASCII可打印字符），可以用字符计数的思路实现O(n)时间复杂度的解法，空间复杂度为O(1)（因为字符集大小固定），更适合处理超长字符串的场景。

内容的提问来源于stack exchange，提问作者Dan Zuzevich