判断两字符串互为排列的Java算法，时空复杂度判定是否正确？

• 时间复杂度标注为*O(nlogn)*是正确的
• 空间复杂度标注为O(1)是错误的，实际空间复杂度为O(n)（n为输入字符串的长度）

时间复杂度判定正确的原因 #

Java标准库中java.util.Arrays.sort()对char类型数组排序的底层实现是双轴快排，平均和最坏时间复杂度均为O(nlogn)。其余步骤：字符串转char数组、排序后生成新字符串、两个字符串相等比对的时间复杂度均为O(n)，低阶复杂度在大O表示中可以忽略，因此整体时间复杂度确实为O(nlogn)。

空间复杂度判定错误的原因 #

O(1)空间的定义是额外占用的内存不随输入规模的变化而变化，你的代码中存在两处随输入规模线性增长的内存占用：

1. sort方法中调用s.toCharArray()会生成一个和输入字符串长度完全相同的新char数组，占用O(n)空间
2. 排序完成后调用new String(c)返回新字符串，同样占用O(n)空间
   即使不计算排序算法底层可能用到的栈空间等额外开销，仅显式创建的两个对象就已经是线性空间占用，因此空间复杂度实际为O(n)。

补充：真正O(1)空间的实现思路 #

如果限定输入字符串的字符集为有限集合（比如标准ASCII字符集，仅128种可能取值），可以用固定长度的计数数组统计字符出现次数，遍历两个字符串比对计数结果即可，这种实现的时间复杂度为O(n)，空间复杂度为O(1)。

你给出的原始代码如下：

/*
Returns true is the two strings are permutations of each other.
Time Complexity; O(nlog n) -> because of the java utils array sort
Space Complexity; O(1)
*/
public boolean isPermutationOptimized(String one, String two) {
    if (one.length() != two.length()) {
        return false;
    }
    return sort(one).equals(sort(two));
}

public String sort(String s) {
    char[] c = s.toCharArray();
    java.util.Arrays.sort(c);
    return new String(c);
}

内容的提问来源于stack exchange，提问作者Davis Ward