给定字符串复杂度的所有置换

Question

我写了这个字符串的所有排列的解法。我有一个关于这个解决方案的时间和空间复杂性的问题。我假设时间复杂度将是O(n)，因为嵌套循环和递归，而空间复杂度将是O(n)因为递归。

我的假设正确吗？如果有，有没有更好的性能解决方案？

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-giving-string/

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'))

Answer 1

长度为n的字符串存在o（n！）置换。

在生成置换中的每个字符串时，通过使用O(n)的for循环来执行O(n)操作

为什么有n！可能并不明显，但您正在递归调用带有剩余字符串的置换(..)函数，因此字符串长度将为n*(n-1)*(n-2)*(n-3)*...*1。