我的算法检查两个字符串是否相互排列正确的时间和 space 复杂度？

Question

    /*
    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);
}

我相信时间复杂度是 O(nlogn)，因为 java.utils 数组排序并且 space 复杂度是常数。

Answer 1

时间复杂度在平均和最坏情况下都是 O(nlogn)。 Space Timsort（使用的排序算法）的复杂度需要额外的 O(n) space：它不是常数复杂度而是线性复杂度。一些参考资料：https://ericmervin.medium.com/what-is-timsort-76173b49bd16

你的算法的复杂度与Timsort的复杂度相同，因为你使用了该算法的两倍。

我的算法检查两个字符串是否相互排列正确的时间和 space 复杂度？

Are the time and space complexity for my algorithm for checking if two strings are permutations of each other correct?

java

big-o

time-complexity