关于两段JS函数时间与空间复杂度的技术咨询与验证

function isCharacterInString(character, string) {
    for (let i = 0; i < string.length; i++) {
        if (character === string[i]) {
            return true;
        }
    }
    return false;
}

function removeDuplicateLetters(string) {
    let filteredString = '';
    for (let i = 0; i < string.length; i++) {
        if (!isCharacterInString(string[i], filteredString)) {
            filteredString += string[i];
        }
    }
    return filteredString;
}

一、分析两段函数的时间与空间复杂度 #

1. isCharacterInString() #

• 时间复杂度：O(n)，n为输入string的长度。最坏情况需遍历整个字符串才能确定目标字符不存在，循环执行次数随字符串长度线性增长。
• 空间复杂度：O(1)，仅使用了变量i，无论输入字符串长度如何，该变量占用的内存始终固定，无额外随输入规模增长的空间开销。

2. removeDuplicateLetters() #

• 时间复杂度：O(n²)，外层循环遍历输入字符串（共n次），每次循环调用isCharacterInString()，而filteredString最长可与输入字符串等长（输入无重复字符时），内层操作最坏时间复杂度为O(n)，因此整体时间复杂度为O(n×n)=O(n²)。
• 空间复杂度：O(n)，filteredString用于存储去重后的字符，最坏情况（输入全为不重复字符）下长度等于输入字符串长度n，空间占用随输入规模线性增长。

二、验证复杂度陈述的正确性 #

• 陈述1：isCharacterInString()中变量“i”的空间复杂度为O(1)，因每次迭代复用同一变量，仅当每次新建“i”时才为O(n)，故该函数整体空间复杂度为O(1)。
  ✅ 正确。代码中let i在循环外初始化，整个循环周期复用同一个变量，内存占用固定；若采用每次迭代创建新变量的写法（如for (const i of ...)）才会是O(n)，当前代码不符合该情况，因此函数整体空间复杂度为O(1)。

• 陈述2：removeDuplicateLetters()的空间复杂度为O(n)，因filteredString变量随输入字符串长度增长，输入越长所需内存越大。
  ✅ 正确。filteredString的最大长度等于输入字符串长度（无重复字符场景），空间占用与输入规模n线性相关，因此空间复杂度为O(n)。

• 陈述3：isCharacterInString()的时间复杂度为O(n)，因for循环执行次数随输入字符串长度增长。
  ✅ 正确。最坏情况需遍历整个字符串，循环次数与输入长度n成正比，时间复杂度为O(n)。

三、问题解答 #

1. removeDuplicateLetters()的时间复杂度是因嵌套循环为O(n²)，还是因输入字符串与filteredString长度此消彼长而为O(n)？ #

是O(n²)。即便filteredString长度随去重操作逐渐增加，但最坏场景下（输入全为不重复字符），filteredString长度会从0增长到n，此时每次调用isCharacterInString()都需遍历整个filteredString，总操作次数为1+2+3+...+n = n(n+1)/2，时间复杂度为O(n²)。即便存在重复字符，时间复杂度的上界仍为O(n²)，因此不能认定为O(n)。

2. 若removeDuplicateLetters()运行时filteredString为随机长度的随机字符串，其时间复杂度是否为O(a*b)？ #

是的。假设输入字符串长度为a，filteredString的平均长度为b，外层循环执行a次，每次内层isCharacterInString()的平均时间复杂度为O(b)，因此整体时间复杂度为O(a×b)。若b为与a无关的常数，复杂度可降至O(a)；若b随a线性增长，则复杂度仍为O(a²)。

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