Время / Пространство Сложность - Как выяснить в этой функции?

Question

Мне нужно рассчитать сложность времени и пространства для этой проблемы, может кто-нибудь помочь мне понять, что это такое и почему?

Я полагаю, что временная сложность для этой проблемы будет O (n ^ 2) из-за 2 функций фильтра. По сути, это было бы аналогично наличию двух циклов for, которые выполняют итерацию по массиву, и поскольку они циклически выполняются в течение заданного промежутка времени, мы знаем, что это будет O (n) для первого фильтра, и добавление еще одного сделает его O (п ^ 2)

Не уверен насчет сложности пространства.

let arr = [1, 2, 2, 4, 4, 5, 6, 7, 7, 8, 9];
const result = arr.filter(x => arr.filter(y => y === x).length > 1)
console.log(result);
// 2, 2, 4, 4, 7, 7

Answer 1

Да, временная сложность равна O(n^2) - например, если arr имеет 10 элементов, алгоритм должен выполнить ~ 100 сравнений до завершения.

Пространственная сложность равна O(n).Например, рассмотрим последнюю итерацию внешнего .filter - почти завершенное построение result занимает в то время O(n) пространство (наихудший случай; эквивалентно стороне ввода arr).Внутренний массив в фильтруемом обратном вызове (который затем будет проверен и возвращен length) также будет, в худшем случае, стороной ввода n.Таким образом, наибольшее пространство, которое будет использоваться в данный момент в любой момент времени, составляет O(2n), что эквивалентно O(n).

Answer 2

Я думаю, что вы правы относительно сложности времени, она равна O (n ^ 2) из-за двух вложенных циклов.

Сложность пространства IMO равна O (n), поскольку вам нужно только n единиц пространствасохранить массив и не выделять дополнительную память.