Какова временная сложность этой функции?

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 немного нечеток, поскольку язык не дает никаких гарантий относительно временной сложности любых операций, а среда выполнения способна сделать некоторые чрезвычайно мощные оптимизации.)