我写了这个字符串所有排列的解决方案。我对这个解决方案的时间和空间复杂度有疑问。 我假设时间复杂度为 O(n3),因为嵌套循环和递归,空间复杂度为 O(n),因为递归。
我的假设正确吗?如果是的话,有没有更好的性能解决方案?
https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
输入:“ABC”
输出:['ABC'、'ACB'、'BAC'、'BCA'、'CAB'、'CBA']
谢谢!
function permutation(string) {
// Basecase
if (string.length < 2) {
return string;
}
var permutations = []; // This array will hold our permutations
for (var i = 0; i < string.length; i++) {
var char = string[i];
// Cause we don't want any duplicates:
// if char is not matched, skip it this time
// otherwise it will generate duplicated string
if (string.indexOf(char) != i) {
continue;
}
var remainingString = string.slice(0,i) + string.slice(i+1,string.length);
var tempResult = permutation(remainingString)
for (var subPermutation of tempResult) {
var result = char + subPermutation
permutations.push(result)
}
}
return permutations;
}
console.log(permutation('ABC'))
最佳答案
长度为 n
的字符串存在 O(n!)
种排列。
在生成排列中的每个字符串时,您通过使用 O(string.length) = O(n)
的 for 循环来执行 O(n)
操作
为什么有 n!
可能并不明显,但您正在使用剩余的字符串递归调用 permutation(..)
函数,因此字符串长度将为 n * (n - 1) * (n - 2) * (n - 3) * ... * 1。
因此,算法的时间复杂度为O(n * n!)
。
其他流行的已知解决方案(基于交换的解决方案,与您的解决方案类似,以及基于下一个排列的解决方案)具有相同的时间复杂度。
关于javascript - 给定字符串的所有排列 - 复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49544791/