这个函数的时间复杂度是多少？

Question

这个算法的时间复杂度是多少？我知道 array.map 有 O(n) 其中 n 是数组的长度。我也读过 string.slice() 也有 O(n) 的时间复杂度。但是，由于切片取决于单词的长度，所以我说时间复杂度为 0(n + m) 是否正确，其中 m 是单词的长度。function sentenceCaps(str) {  if (!str) {    return new Error('empty string');  }  let arr = str.toLowerCase().split(' ');  let results = arr.map(word => {return word[0].toUpperCase()+ word.slice(1)});  return results.join(' ');}

Answer 1

这个函数的时间复杂度是多少？

O( n )。

我说时间复杂度为 0(n + m) 是否正确，其中 m 是单词的长度。

不，因为m大致等于n。即使我们假设结果的长度String.slice()是 O( n )，切片的字母总数也是n 的一小部分，因此它已经被计入了复杂性。实际上，这可能是一个恒定时间的操作。

（分析任何 Javascript 代码的时间复杂度有点模糊，因为该语言不保证任何操作的时间复杂度，并且运行时能够进行一些非常强大的优化。）