Javascript - временная и пространственная сложность соединения и объединения внутри цикла

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

Объяснение

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), где n — длина x?

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

  3. Изменяют ли .concat(), .splice() или .split() временную сложность, поскольку они вложены в цикл for? А если нет, то изменяют ли они временную сложность алгоритма и насколько?

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

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


javascript time-complexity big-o complexity-theory space-complexity
person Community    schedule 03.12.2018    source источник
comment
На самом деле, если бы мы действительно знали временную сложность объединения, разделения или соединения, то это, очевидно, повлияло бы на общую временную сложность вашего алгоритма. Но поскольку мы этого не делаем, мы будем рассматривать их как постоянную операцию, O (1), что фактически поддерживает операцию цикла на уровне O (N) - в худшем случае. Сложность пространства составляет O(1), потому что мы не создаем новое хранилище (в данном случае count) для каждой операции цикла, а просто обновляем его. ИМО, это справедливое решение, так как я не знаю, каковы ограничения для вашей проблемы.   -  person Caleb Lucas    schedule 04.12.2018
comment
@CalebLucas Но, поскольку мы этого не делаем, мы бы рассматривали их как постоянную операцию - должны ли мы? Будет ли эта проблема все еще иметь смысл в этом случае? Кроме того, спецификация ECMA дает подсказки относительно того, что это такое.   -  person meowgoesthedog    schedule 04.12.2018
comment
@meowgoesthedog мы должны? - Я чувствую, что это зависит от цели. Эти функции оптимизируются во время выполнения движком javascript. Если цель состоит в том, чтобы действительно вникнуть в специфику каждой функции и их применения в заданном сценарии, то, конечно, учет их временной сложности будет иметь первостепенное значение.   -  person Caleb Lucas    schedule 04.12.2018
comment
@CalebLucas, вы правы, split(), concat() и т. д. были оптимизированы движком JS. Однако это не означает, что для этих операций нет временной/пространственной сложности. На это есть 2 ответа, основанных на намерении вопроса. Если это для интервью, то нам нужно учитывать временную и пространственную сложность этих методов. Если это для приложения, вам не о чем беспокоиться. Глядя на вопрос, кажется, что это вопрос интервью, для этого OP необходимо учитывать эти вещи, потому что следующий вопрос будет со сложностью для этого алгоритма.   -  person Viral    schedule 02.03.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

person kaya3    schedule 28.01.2020
comment
splice(i, 1) не является O(1) для хеш-таблицы индекс -> значение, потому что она должна перенумеровать все. - person Ry-♦; 28.01.2020