javascript - 这个函数的时间复杂度是 O(N) 还是 O(N^2)？

Question

我正在尝试确定以下函数的时间复杂度。

该函数反转字符串中单词的顺序，然后反转单词中字母的顺序。

例如:

“天空是蓝色的”=>“eulb si yks eht”

var reverseString = function(s) {
  let str = s.split(' ')
  let word;
  let wordRev;
  let result = [];
  let countI = 0
  let countJ = 0    

  //lets call this loop "i"
  for(let i=str.length-1; i>=0; i--) {
    word = str[i]
    wordRev = ""
    countI +=1

    //lets call this loop "j"      
    for(let j=word.length-1; j>=0; j--) {
      wordRev += word[j]
      countJ+=1
    }
    result.push(wordRev)
  }
  return result.join(" ")
};

虽然有两个嵌套循环，但我相信时间复杂度是O(n)，我将举两个场景作为例子。

•     Scenario 1:
   ⁃    s.length: 22
   ⁃    input: “thisisreallylongstring”
   ⁃    str: [“thisisreallylongstring”]
   ⁃    i loop count total: 1
   ⁃    j loop count total: 22
•   Scenario 2
   ⁃    s.length = 11
   ⁃    input: “s t r i n g”
   ⁃    str: [“s”, “t”, “r”, “i”, “n”, “g”]
   ⁃    j loop count total: 6
   ⁃    i loop count total: 6

循环 i 和 j 的总计数大致等于输入的长度，这让我相信即使有两个嵌套循环，它仍然是 O(n) 复杂度。

我的思路错了吗？

Answer 1

这里有两个因素在起作用:

1. 您的算法本身是 O(n)。在每个内部循环中处理的子字符串是不相交的。也就是说，您有两个嵌套循环，但在内循环中处理的字符串部分永远不会被外循环中的单独迭代重复。每个内部循环都有自己单独的子字符串，当您将它们加在一起时，它的复杂度为 O(n)。

2. 以这种方式追加字符串使得算法复杂度为 O(n^2)。字符串是不可变的，因此每次调用 wordRev += word[j] 都会创建一个全新的字符串。在最坏的情况下，例如对于 "thisisreallylongstring"，您最终会创建 "g"、"gn"、"gni"、... 作为中间字符串。将它们相加是 O(n^2)。

所以总的答案是 O(n^2)。