生成字符串全排列的JS函数时间复杂度分析及优化咨询

一、时间复杂度分析 #

你的这个全排列函数时间复杂度为 O(n² × n!)，具体原因如下：

1. 生成所有全排列的基础数量是 n!（n为输入字符串长度），这是不可避免的开销。
2. 递归过程中每次调用的splice操作是**O(k)**复杂度（k为当前sArr的长度）——数组是连续存储结构，splice会移动目标位置后的所有元素，这是性能瓶颈之一。
3. 对于每个长度为k的子问题，循环会执行k次，每次都包含O(k)的splice操作，单个子问题的时间开销为O(k²)。累加所有子问题的开销后，最终总时间复杂度就是O(n² × n!)。

二、优化空间 #

1. 用交换元素替代splice，将时间复杂度降至O(n × n!) #

splice的O(k)移动开销是主要性能短板，我们可以通过交换数组元素的方式避免移动数组元素，每次交换操作是O(1)，直接把时间复杂度降到O(n × n!)。

优化后的TypeScript代码：

function generateAllPerms(s: string) {
    const result: string[] = [];
    const sArr = [...s];
    
    function perm(start: number) {
        if (start === sArr.length) {
            result.push(sArr.join(''));
            return;
        }
        for (let i = start; i < sArr.length; i++) {
            // 交换当前元素与起始位置元素
            [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
            perm(start + 1);
            // 回溯，交换回原位置
            [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
        }
    }
    
    perm(0);
    return result;
}

优化后的JavaScript代码：

function generateAllPerms(s) {
    const result = [];
    const sArr = [...s];
    
    function perm(start) {
        if (start === sArr.length) {
            result.push(sArr.join(''));
            return;
        }
        for (let i = start; i < sArr.length; i++) {
            [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
            perm(start + 1);
            [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
        }
    }
    
    perm(0);
    return result;
}

console.log(generateAllPerms('abc'));

2. 处理重复字符，避免生成重复排列 #

如果输入字符串包含重复字符（比如'aab'），当前算法会生成大量重复排列。可以在循环时跳过重复元素，减少不必要的递归：

以TypeScript为例，修改循环部分：

function perm(start: number) {
    if (start === sArr.length) {
        result.push(sArr.join(''));
        return;
    }
    const used = new Set<string>();
    for (let i = start; i < sArr.length; i++) {
        if (used.has(sArr[i])) continue;
        used.add(sArr[i]);
        [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
        perm(start + 1);
        [sArr[start], sArr[i]] = [sArr[i], sArr[start]];
    }
}

3. 减少join的开销 #

当前每次完成排列时调用curr.join('')，可以在递归过程中直接拼接字符串（用字符串代替数组存储当前排列），避免数组转字符串的开销：

示例（JavaScript版本）：

function generateAllPerms(s) {
    const result = [];
    
    function perm(curr, remaining) {
        if (remaining.length === 0) {
            result.push(curr);
            return;
        }
        for (let i = 0; i < remaining.length; i++) {
            const nextCurr = curr + remaining[i];
            const nextRemaining = [...remaining.slice(0, i), ...remaining.slice(i+1)];
            perm(nextCurr, nextRemaining);
        }
    }
    
    perm('', [...s]);
    return result;
}

不过这种方式会生成新的数组和字符串，适合小长度输入；如果输入字符串较长，还是交换元素的方式性能更优。

内容的提问来源于stack exchange，提问作者kataya1