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

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 代码的时间复杂度有点模糊，因为该语言不保证任何操作的时间复杂度，并且运行时能够进行一些非常强大的优化。）