我正在尝试确定以下功能的时间复杂度。
该函数反转字符串中单词的顺序，然后反转单词中字母的顺序。
例如：
“天空是蓝色的” =>“ 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）。
我的思路是否正确？
最佳答案
这里有两个因素在起作用：
您的算法本身为O（n）。在每个内部循环中处理的子字符串是不相交的。也就是说，您有两个嵌套循环，但是在内部循环中处理的字符串部分永远不会通过外部循环中的单独迭代重复进行。每个内部循环都有自己的单独子字符串，将它们加在一起时，它就是O（n）。
通过这种方式附加字符串使算法为O（n ^ 2）。字符串是不可变的，因此每次调用wordRev += word[j]都会创建一个全新的字符串。在最坏的情况下（例如对于"thisisreallylongstring"），最终会创建"g", "gn", "gni", ...作为中间字符串。将它们加在一起就是O（n ^ 2）。
因此，总的答案是O（n ^ 2）。