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

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 数组排序和空间复杂度是恒定的。

标签： javatime-complexitybig-o

Answer 1

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

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