Пространственно-временная сложность итерации и объединения строк в javascript - PullRequest
Новая
       8

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

0 голосов
/ 17 марта 2020

По этому вопросу меня не особо интересует правильный ответ, а скорее объяснение, так как я видел противоречивые ответы в inte rnet для этого.

Вот примерная проблема: 

function reverseStr(str) {
  let output = ""

  for (var i = str.length-1; i >= 0; i--;) {
    output += str[i]
  }

  return output


}

Что такое сложность пространства и времени?

Космическая сложность. Мое предположение # 1 состоит в том, что сложность пространства равна O (n). По мере роста нашей входной строки нам потребуется сохранять еще одну копию (переменный вывод) того же размера, прежде чем возвращать ее. Однако я путаюсь с тем фактом, что строки являются неизменяемыми, а это означает, что технически новая копия строки создается каждый раз, когда мы нажимаем новый символ в нашем for-l oop и объединяем. Конечно, нам больше не нужна наша старая строка, поэтому она будет собирать мусор (?) ... но хранится ли она в памяти какое-то время? Даже если он будет храниться в памяти, я не думаю, что это повлияет на фактическую сложность этой проблемы в пространстве, но, опять же, мне больше интересно узнать подробности здесь.

Сложность времени. Мое предположение # 2 состоит в том, что сложность времени здесь равна O (n). Мы рассмотрим каждый символ один раз в l oop (эта часть ясна). Затем мы выполняем конкатенацию. Однако я предполагаю, что канкатизация 'a' + 'bcd' занимает то же время, что и конкатенация 'a' + 'bcdefghijklmn' ... или эта прямая конкатенация линейно занимает больше времени по мере увеличения размера двух строк? Если это так, то сложность по времени будет O (n ** 2) ...

Большое спасибо.

...