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

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

0 голосов
/ 03 декабря 2018

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

Пояснение 

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. Какова пространственная сложность этого алгоритма?

...