javascript - 比较两个字符串的时间复杂度

Question

ff函数o(nlogn)的运行时间如何？

function isPermutation(a, b) {
    if (a.length !== b.length) {
        return false;
    }
    return a.split("").sort().join() === b.split("").sort().join();
}

你不是检查两个字符串的长度，还是取决于排序的实现？

Answer 1

根据Permutation的定义, 当且仅当第一个字符串中的所有字符也在第二个字符串中时，一个字符串是另一个字符串的排列。

示例:"answer" 是"awerns" 的排列。

因此，要编写一种算法来检查一个字符串是否是另一个字符串的排列，您所要做的就是:

1. 检查两个字符串的长度是否相同，如果不相同则返回false。

2. 对于字符串一中的每个字母，检查它是否也存在于字符串二中。

上述算法的运行时间将为但您可以使用排序来解决同样的问题:

1. 检查两个字符串的长度是否相同，如果不相同则返回false。

2. 对两个字符串进行排序

3. 字符串中的每个字符按顺序排列，如 stringOne[i] == stringTwo[i]

所以在这一个中，如果你使用像 Quick Sort 这样好的排序算法或 Merge Sort整体运行时间将为