为什么两个看似相似的数组方法导致时间复杂度截然不同？

Question

我正在解决一个提示如下的算法问题：

"给定一个字符串s，找出最长的不带重复字符的子串的长度。"

我有两个可接受的解决方案，如下所示：

function lengthOfLongestSubstring(s: string): number {
    let longestStr = '';
    let maxLength = 0;

 for (let i = 0; i < s.length; i += 1) {
       //solution 1
         if (longestStr.split('').includes(s[i])) {
             longestStr = longestStr.slice(longestStr.split('').indexOf(s[i]) + 1);
         }
          longestStr += s[i];
        
         if (longestStr.length > maxLength) {maxLength = longestStr.length} 
 
       // solution 2 
        longestStr += s[i];
        if(longestStr.indexOf(s[i]) !== longestStr.length - 1) {
            longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1)
        }

        if (longestStr.length > maxLength) {maxLength = longestStr.length} 
  }
  return maxLength;

}

两种解决方案的区别在于是在if语句之前还是之后引入这段代码。

longestStr += s[i];

代码中唯一会导致 time/space 复杂性的区别是各自 if 语句中的代码。

解决方案 1 的性能更好：214 毫秒，44.9MB

解决方案 2 明显更差：607 毫秒，47MB

解决方案一：根据 Running time of string.Split method ， .split 方法具有 O(n) 时间复杂度。 .includes 方法必须有 O(n) 因为它循环一次。

方案二：根据 What is the time complexity of javascript's array.indexOf?，.indexOf 有 O(n)。 .length 是在所有可枚举的 Javascript 对象（数组）中都可以访问的方法，在数组中查找是 O(1)。

除非我上面的时间复杂度不正确，否则解决方案 2 似乎会花费更少的时间。然而，完全相反。

请帮我理解，谢谢

Answer 1

你说得对。解决方案 1 的性能应该更差。至少根据我的测试，确实如此：

    function lengthOfLongestSubstring(s) {
    let longestStr = ''
    let maxLength = 0

    for (let i = 0; i < s.length; i += 1) {
        //solution 1
        if (longestStr.split('').includes(s[i])) {
            longestStr = longestStr.slice(
                longestStr.split('').indexOf(s[i]) + 1
            )
        }
        longestStr += s[i]

        if (longestStr.length > maxLength) {
            maxLength = longestStr.length
        }
    }
    return maxLength
}
function lengthOfLongestSubstring2(s) {
    let longestStr = ''
    let maxLength = 0

    for (let i = 0; i < s.length; i += 1) {
        // solution 2
        longestStr += s[i]
        if (longestStr.indexOf(s[i]) !== longestStr.length - 1) {
            longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1)
        }

        if (longestStr.length > maxLength) {
            maxLength = longestStr.length
        }
    }
    return maxLength
}
let s1 = ''
const slen = 1000000
const letters = 'abcdeghijklmnop'
for (let i = 0; i < slen; i++) {
    s1 = s1 + letters[Math.random() * letters.length]
}
console.time('solution1')
console.log(lengthOfLongestSubstring(s1))
console.timeEnd('solution1')
console.time('solution2')
console.log(lengthOfLongestSubstring2(s1))
console.timeEnd('solution2')
// result: solution 1: 1.484s, solution 2: 317ms

你看到同样的东西了吗？

为什么两个看似相似的数组方法导致时间复杂度截然不同？

Why does two seemingly similar array methods result in drastically different time complexity?

javascript

arrays

performance

time-complexity