Временная сложность комбинации строк с разделенной картой - PullRequest
Новая
       13

Временная сложность комбинации строк с разделенной картой

0 голосов
/ 21 октября 2019

Мне интересно, как рассчитать временную сложность такой комбинации: 

"some string"
   .split(" ") // O(n)
   .map( 
      word => doSomething(word) // word length = j, doSomething(word) => O(j)
    ) // O(n * j) => O(n^2) ???

doSomething - это функция линейной сложности, не представляющая, что она делает.

Итак, согласно Большой O встроенной функции разделения javascript , временная сложность .split(" ") будет O(n)

На следующей строке у нас есть массив .map для слов, который в худшем случаерегистр может быть O(n/2) => O(n), когда у нас есть все слова, содержащие один символ.

Внутри функции карты мы делаем некоторую операцию над словом длиной j => O(j). Учитывая, что это слово может иметь размер полной строки (без пробелов) O(j) => O(n)

В результате мы имеем общую сложность времени O(n^2)

НО, если у нас наихудший случай на .mapшаг O(n) тогда у нас не может быть худшего случая внутри карты, потому что общая сумма всех слов длины равна размеру входной строки. Таким образом, мы не можем преобразовать O(j) to O(n)

Какова будет сложность времени?

Обновление

Хорошо, я сделал несколько экспериментальных измерений, и вот что я 'у меня на компьютере https://www.wolframalpha.com/input/?i=listplot%5B%7B%7B10%2C+0.015%7D%2C%7B100%2C+0.1%7D%2C%7B1000%2C+0.72%7D%2C%7B10000%2C+8.5%7D%2C%7B100000%2C+67.89%7D%2C+%7B1000000%2C+642.60%7D%2C+%7B10000000%2C+6657.4%7D%2C+%7B100000000%2C+70076.01%7D+%7D%5D

ось X => время мс

ось Y => длина входной строки

данные, сгенерированные случайным образом

сложностьявно линейный.

1 Ответ

1 голос
/ 22 октября 2019

Код O (n), где n - длина строки:

Я бы согласился с тем, что split означает O (n).

Интересная часть - этоmap. Здесь вы приводите правильные аргументы для верхнего предела сложности. Это правда, что код также O (n²) (обратите внимание, что O (n) является подмножеством O (n²), тривиально, так что нет никакого противоречия). Однако, более точная оценка может быть сделана. Обратите внимание, что наихудшие случаи для вашей оценки не могут возникнуть одновременно:

  • Если одно слово имеет размер всей строки, вы не можете иметь более одного слова
  • Если у вас есть один символ на слово (максимальное количество слов), у вас есть именно этот символ, один символ на слово

Сумма символов каждого слова всегда будет длиной отправления. Сложность составляет O (сумма длин символов всех слов), и вместо оценки как длины символов, так и количества слов в худшем случае мы замечаем, что это просто O (n).

В качестве последовательной цепочкипостоянное количество операций O (n) по-прежнему равно O (n), мы получаем вышеупомянутую общую сложность O (n), где n - количество символов.

...