Javascript - Пространственно-временная сложность склейки и конкатов внутри цикла

Question

У меня есть проблема, которая требует преобразования строки в другую путем добавления к ней копий ее начального значения. Проблема позволяет удалить отдельные символы в некоторых местах.

объяснение

let x = "abba"; // First string
let y = "aba" // Second initial string

y("aba") => remove last "a" => y("ab") => y+initialY = "ab"+"aba" => 
y("ababa") => remove char at index 2 => y("abba") => y == x => sucess

Мой алгоритм успешно решает проблему:

let x = "abbbbcccaaac"
let y = "abc"

let xArr = x.split('')
let yArr = y.split('')

let count = 0;

for (let i = 0; i < xArr.length; i++) {
  if(yArr[i] == undefined) {
    yArr = yArr.concat(y.split('')  
    count++;
  }
  if(xArr[i] != yArr[i]) {
    yArr.splice(i, 1);
    i--;
  }
}

console.log("Output is:", yArr.join(''))
console.log("Appends in order to transform:", count)

Алгоритм работает так, как задумывалось, однако я не уверен относительно его временного и пространственного усложнения, а главное - эффективности.

1. Этот алгоритм в O(n) сложность времени, где п длина x?

2. Если это не O(n)Может ли проблема быть решена в O(n) время?

3. Есть ли .concat(), .splice() или же .split() как-то изменить сложность времени, так как они вложены в цикл for? Что, если они не были, они все еще изменяют временную сложность алгоритма и насколько?

4. Учитывая правила этой проблемы, это эффективный способ ее решения?

5. Какова пространственная сложность этого алгоритма?

Answer 1

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

Итак, нет окончательной временной сложности для spliceчтобы удалить один элемент из массива. Мы можем сказать, что удаление одного элемента занимает линейное время для динамического массива и, как указывает @Ry- в комментариях, также линейное время для хеш-таблицы из-за необходимости перенумеровать более поздние индексы. Мы также можем сказать, что весьма вероятно, что используется одна из этих двух структур данных, и ни одна разумная реализация не займет больше, чем линейное время, чтобы сделатьsplice.

В любом случае худший случай для вашего алгоритма - это когда x = 'aa...aa' а также y = 'abb...bb', т.е. x есть n копий 'a', а также y является 'a' за которым следуют (m - 1) копии 'b'.

Для динамического массива или хеш-таблицы временная сложность только дляspliceопераций составляет O(нм²). Это потому, что внешний цикл повторяется O(нм) раз (обратите внимание наi-- внутри цикла, что происходит каждый раз, когда буква 'b' необходимо удалить), а splice операция требует сдвига или перенумерации O(m) элементов в yArr после индекса i.

Но предположим, что используется какая-то более экзотическая структура данных, которая поддерживает удаление элемента за сублинейное время (например, список пропуска). В этом случае вышеупомянутое дает только O(нм) раз сложность операции "удалить". Но мы не посчиталиconcatвсе же; это создает новую структуру данных и копирует в нее каждый элемент, что по-прежнему занимает линейное время.concat вызывается O(n) раз и занимает в среднем O(n+ m) времени на вызов, поэтому сложность только concat операций - O(n² + нм).

Таким образом, временная сложность, скорее всего, составит O(n² + nm²) и, конечно же, не менее O(n² + nm); не линейный.

---

Сложность пространства равна O(n), поскольку длина yArr никогда не бывает более чем вдвое длиннее xArr.